#include <stack>
#include <iostream>
#include <cstdio>
#include <ctime>

#include "ResultGraphTable.h"
#include "Utilities.h"
#include "SpaEnumTranslator.h"

std::string ResultGraphTable::ANY_SYNONYM = "_ANY_SYNONYM_";

ResultGraphTable::ResultGraphTable(void)
{
}


ResultGraphTable::~ResultGraphTable(void)
{
}

// Is this synonym in the table?
bool ResultGraphTable::isSynonymInTable(const std::string& synonym) {
	return Utilities::isKeyInMap_TypeClass(mHeaders, synonym);
}

// Returns the list of result indexes for this synonym
std::vector<int>& ResultGraphTable::getResultIndexesForSynonym(const std::string& synonym, DesignEntityType synEntityType, PKB *pkb) {
	if (!isSynonymInTable(synonym)) {
		// Return all indexes if synonym doesn't exist in the table
		std::vector<int>& allIndexes = getAllIndexes(synEntityType, pkb);
		return allIndexes;
	}
	std::vector<int>* resultIndexes = new std::vector<int>();
	NodeMap* columnNodes = mColumns.at(synonym);
	for (auto it = columnNodes->begin(); it != columnNodes->end(); it++) {
		const ResultGraphTableNode* columnNode = it->second;
		int nodeValue = columnNode->getNodeValue();
		resultIndexes->push_back(nodeValue);
	}
	return *resultIndexes;
}

// Returns the list of result nodes for the specified synonym, with which traversal through the graph can be done (e.g. for finding tuples)
std::vector<ResultGraphTableNode>& ResultGraphTable::getResultNodesForSynonym(const std::string& synonym) {
	std::vector<ResultGraphTableNode> *resultNodes = new std::vector<ResultGraphTableNode>();
	if (!isSynonymInTable(synonym)) {
		// Return empty vector if synonym doesn't exist in the table
		return *resultNodes;
	}
	NodeMap* columnNodes = mColumns.at(synonym);
	for (auto it = columnNodes->begin(); it != columnNodes->end(); it++) {
		const ResultGraphTableNode* columnNode = it->second;
		resultNodes->push_back(*columnNode);
	}
	return *resultNodes;
}

// Performs the main algorithm and updating of the resultGraphTable for the specified synonym1 and synonym2, 
// using the trueRelationshipPairs which are basically the pairs of synonym1 and synonym2 such that the relationship being evaluated holds.
// This is the function which will perform column insertion, link creation, graph traversal and link deletion
bool ResultGraphTable::updateWithNewRelationship(const std::string& synonym1, const std::string& synonym2, 
	RelationshipType relType, PKB *pkb, SynonymTable *synonymTable) {

		if (synonym1 == synonym2) {
			cout << "synonym1 = " << synonym1 << " & synonym2 = " << synonym2 << endl;
			// Synonyms are equal
			updateWithNewRelationshipForEqualSynonyms(synonym1, synonym2, relType, pkb, synonymTable);

		} else if ( !isSynonymInTable(synonym1) && !isSynonymInTable(synonym2)) {
			// Both synonym1 and synonym2 not in table
			updateWithNewRelationshipForBothSynonymsNotInTable(synonym1, synonym2, relType, pkb, synonymTable);

		} else if (isSynonymInTable(synonym1) && isSynonymInTable(synonym2)) {
			// Both synonym1 and synonym2 in table
			updateWithNewRelationshipForBothSynonymsInTable(synonym1, synonym2, relType, pkb, synonymTable);

		} else if (isSynonymInTable(synonym1)) {
			// synonym1 in table but synonym2 not in table
			updateWithNewRelationshipForLeftSynonymInTable(synonym1, synonym2, relType, pkb, synonymTable);
			
		} else {
			// synonym1 not in table but synonym2 in table
			updateWithNewRelationshipForRightSynonymInTable(synonym1, synonym2, relType, pkb, synonymTable);
		} 

		// The relationship we just updated is true only if there is at least one node of synonym1 and synonym2 left in the table
		return (isThereAtLeastOneNodeOfSynonymName(synonym1) && isThereAtLeastOneNodeOfSynonymName(synonym2));
}

// Updates the graph-table for the specified synonym using the given badIndexesOfSynonym.
// If the synonym was not previously in the table, adds it to the table with all possible indexes first, using the pkb->
// Finally, look through them and delete those indexes which are bad (contained in badIndexesOfSynonym)
bool ResultGraphTable::updateSynonymWithBadResults(const std::string& synonym, std::vector<int>& badIndexesOfSynonym,
	PKB *pkb, SynonymTable *synonymTable) {
		if ( !Utilities::isKeyInMap_TypeType(mHeaders, synonym)) {
			// synonym previously not in the table, so we add it with ALL indexes in first
			initializeColumn(synonym);

			DesignEntityType synonymEntityType = synonymTable->getDesignEntityType(synonym);
			std::vector<int>& synonymIndexes = getAllIndexes(synonymEntityType, pkb);

			for (unsigned int i = 0; i < synonymIndexes.size(); i++) {
				int synonymIndex = synonymIndexes.at(i);
				addResultNodeUniquelyToColumn(synonym, synonymIndex);
			}
		}

		// Delete those indexes which are bad
		std::vector<ResultGraphTableNode> nodesToDelete;
		EdgeMap edgesToDelete;
		NodeMap* nodeColumn = mColumns.at(synonym);
		for (unsigned int i = 0; i < badIndexesOfSynonym.size(); i++) {
			ResultGraphTableNode *badNode = new ResultGraphTableNode(synonym, badIndexesOfSynonym.at(i));
			const std::string& badNodeId = badNode->getNodeIdentifier();
			if (nodeColumn->find(badNodeId) != nodeColumn->end()) {
				// Only delete if the bad node exists in the column
				nodesToDelete.push_back(*badNode);
				EdgeMap* badEdges = getEdgesOfNode(*badNode, ANY_SYNONYM);
				// TODO optimize by deleting the edges immediately.
				for (auto it = badEdges->begin(); it != badEdges->end(); it++) {
					const edge& badEdge = it->second;
					edgesToDelete.insert( std::pair<string, edge>(it->first, badEdge) );
				}
			}
		}
		// Destroy all the edges (recursively checks the nodes and so on to delete them)
		destroyEdges(edgesToDelete);
		// Then delete the bad nodes
		for (unsigned int i = 0; i < nodesToDelete.size(); i++) {
			deleteNode(nodesToDelete.at(i));
		}

		return isThereAtLeastOneNodeOfSynonymName(synonym);
}

// Updates the graph-table for the specified synonym using the given goodIndexesOfSynonym.
// If the synonym was not previously in the table, adds it to the table with all possible indexes first, using the pkb->
// Finally, look through them and delete those indexes which are not good (not contained in goodIndexesOfSynonym)
// NOTE: This method ends up calling updateSynonymWithBadResults, so calling updateSynonymWithBadResults immediately is faster.
bool ResultGraphTable::updateSynonymWithGoodResults(const std::string& synonym, std::vector<int>& goodIndexesOfSynonym, PKB *pkb, SynonymTable *synonymTable) {
	// Just get all the indexes I of the synonym in this table,
	// find all the bad indexes (those in I but not in the goodIndexesOfSynonym)
	// use updateSynonymWithBadResults()
	std::vector<int> badIndexes;
	DesignEntityType synonymEntityType = synonymTable->getDesignEntityType(synonym);
	std::vector<int>& resultIndexesOfSynonym = getResultIndexesForSynonym(synonym, synonymEntityType, pkb);

	std::unordered_map<int, bool> goodIndexMap;
	// insert all good indexes into unordered_map,
	for (unsigned int i = 0; i < goodIndexesOfSynonym.size(); i++) {
		goodIndexMap.insert(std::pair<int, bool>(goodIndexesOfSynonym.at(i), true));
	}
	// check resultIndexesOfSynonym for bad indexes (using the goodIndexMap)
	for (unsigned int i = 0; i < resultIndexesOfSynonym.size(); i++) {
		int resultIndex = resultIndexesOfSynonym.at(i);
		if ( !Utilities::isKeyInMap_TypeType(goodIndexMap, resultIndex)) {
			// is a bad index!
			badIndexes.push_back(resultIndex);
		}
	}

	return updateSynonymWithBadResults(synonym, badIndexes, pkb, synonymTable);
}

void ResultGraphTable::performTraversalForRelationshipEvaluation(PKB *pkb, SynonymTable *synonymTable,
	RelationshipType relType, const std::string& synonym1, const std::string& synonym2, 
	const ResultGraphTableNode * const startingNode, const ResultGraphTableNode *currentNode, 
	EdgeMap *edgesToDestroy, EdgeMap *edgesToSave, PathMap& pathMap) {
		//cout << "DEBUGGING: performTraversalFor... synonym1: " << synonym1 << " synonym2: " << synonym2 << 
		//	" startingNode: " << startingNode->getNodeIdentifier() << endl;
		if (synonym1 == synonym2) {
			// If they are the same synonym, we merely check the startingNode against the startingNode whether the relationship holds
			int startingNodeValue = startingNode->getNodeValue();
			DesignEntityType startingNodeSynonymType = synonymTable->getDesignEntityType(synonym1);
			linkNodes(*(new ResultGraphTableNode(synonym1, startingNodeValue)), *(new ResultGraphTableNode(synonym1, startingNodeValue)));
			if ( !checkIfIsTrueRelationship(pkb, relType, startingNodeValue, startingNodeValue, startingNodeSynonymType, startingNodeSynonymType)) {
				EdgeMap* startingNodeEdges = getEdgesOfNode(*startingNode, ANY_SYNONYM);
				for (auto it = startingNodeEdges->begin(); it != startingNodeEdges->end(); it++) {
					const edge& edgeToDestroy = it->second;
					edgesToDestroy->insert( std::pair<string, edge>(getEdgeIdentifier(edgeToDestroy), edgeToDestroy) );
				}
			}
			return;
		}

		// OPTIMIZATION
		bool isTimeConsumingRelType = isTimeConsumingRelationship(relType);
		std::vector<int> *synonym2TrueIndexes; // to be used only if the relType is time-consuming
		std::unordered_map<int, bool> *synonym2TrueIndexesMap; // to be used only if the relType is time-consuming
		if (isTimeConsumingRelType) {
			synonym2TrueIndexes = new std::vector<int>();
			synonym2TrueIndexesMap = new std::unordered_map<int, bool>();
			synonym2TrueIndexes = &getTrueRelationshipSynonym2IndexesForGivenSynonym1Index(pkb, 
																synonymTable, relType, 
																synonym1, synonym2,
																startingNode->getNodeValue());
			unsigned int synonym2TrueIndexesSize = synonym2TrueIndexes->size();
			for (unsigned int i = 0; i < synonym2TrueIndexesSize; i++) {
				int synonym2Index = synonym2TrueIndexes->at(i);
				synonym2TrueIndexesMap->insert( std::pair<int, bool>(synonym2Index, true) );
			}
		}

		std::unordered_map<std::string, bool> nodeVisitedMap;
		std::stack<const edge*> edgesStack;
		std::string prevNodeSynonymName = ""; // so that edges of the node we just came from is not traversed
		const std::string& currentNodeSynonymName = currentNode->getSynonymName();
		const std::string& nextNodeSynonymName = pathMap.at(currentNodeSynonymName);
		const EdgeMap* currentEdges = getEdgesOfNode(*currentNode, nextNodeSynonymName);
		for (auto it = currentEdges->begin(); it != currentEdges->end(); it++) {
			const edge *e = &it->second;
			//cout << "DEBUGGING: Pushed edge: " << getEdgeIdentifier(*e) << endl;
			edgesStack.push(e);
		}
		// Mark currentNode as visited because edges have been added to the stack
		nodeVisitedMap.insert(std::make_pair(currentNode->getNodeIdentifier(), true));

		// to be used at the end to choose which edges to destroy
		std::stack<const edge*> edgesToDestroyTemp;
		// maintain a stack of nodes that we are traversing
		std::stack<const ResultGraphTableNode*> nodeStack;
		nodeStack.push(currentNode);

		/*cout << "DEBUGGING: nodeStack: ";
		std::vector<const ResultGraphTableNode*> tempNodeList;
		std::stack<const ResultGraphTableNode*> tempNodeStack = nodeStack;
		while ( !tempNodeStack.empty()) {
			const ResultGraphTableNode* node = tempNodeStack.top();
			tempNodeStack.pop();
			tempNodeList.push_back(node);
		}
		for (int i = (int) tempNodeList.size() - 1; i >= 0; i--) {
			const ResultGraphTableNode* node = tempNodeList.at(i);
			cout << node->getNodeIdentifier() << " ";
		}
		cout << endl;*/

		// Keep traversing, looking for nodes of synonym2
		while ( !edgesStack.empty()) {
			// Pop the edge off the stack and into a edgesToDestroyTemp stack of edges,
			// traverse the edge to the node that is not yet visited,
			// check if it is a node of synonym2,
			// if it is not, 
			//		then we add all the edges of the node which have at least one side which has not been visited in advance,
			//		keep track of the number of edges added, and if no edges are added, then edgesToDestroyTemp must be popped
			//		off until it is empty (because this is a leaf*) or the top edge has one of its nodes the same as one of the nodes in the next edge we
			//		will traverse.
			// if it is,
			//		then we do not add any edges of the node, but instead check if the relationship is true.
			//		if it is,
			//			then we pop off ALL edges from edgesToDestroyTemp into a edgesToSave set.
			//		if it is not, 
			//			then we pop off from edgesToDestroyTemp
			//			until it is empty or the top edge has one of its nodes the same as one of the nodes in the next edge we 
			//			will traverse. Add all the popped edges into the edgesToDestroy set. 

			// Pop the edge off the stack and into a edgesToDestroyTemp stack of edges
			const edge *currentEdge = edgesStack.top();
			edgesStack.pop();
			edgesToDestroyTemp.push(currentEdge);

			// traverse the edge to the node that is not the one we are on currently
			prevNodeSynonymName = currentNode->getSynonymName();
			const ResultGraphTableNode* leftNode = currentEdge->leftNode;
			const ResultGraphTableNode* rightNode = currentEdge->rightNode;
			const std::string& leftId = leftNode->getNodeIdentifier();

			if (leftId == currentNode->getNodeIdentifier()) {
				// leftNode is the currentNode, so traverse right
				currentNode = rightNode;
			} else {
				// leftNode is NOT the currentNode, so traverse there (left)
				currentNode = leftNode;
			}
			nodeStack.push(currentNode);

			// Add the startingNode to badEdgeCheckingNodesPtrMap for tuples evaluation
			if ( !Utilities::isKeyInMap_TypeType(mBadEdgeCheckingNodeMapPtrMap, currentNode->getNodeIdentifier())) {
				mBadEdgeCheckingNodeMapPtrMap.insert( 
					std::make_pair(currentNode->getNodeIdentifier(), new BadEdgeCheckingNodeMap()));
			}
			BadEdgeCheckingNodeMap *badEdgeCheckingNodeMap = mBadEdgeCheckingNodeMapPtrMap[currentNode->getNodeIdentifier()];
			badEdgeCheckingNodeMap->insert( std::make_pair(startingNode, true) );

			/*cout << "DEBUGGING: Traversing to " << currentNode->getNodeIdentifier() << endl;
			cout << "DEBUGGING: nodeStack: ";
			std::vector<const ResultGraphTableNode*> tempNodeList;
			std::stack<const ResultGraphTableNode*> tempNodeStack = nodeStack;
			while ( !tempNodeStack.empty()) {
				const ResultGraphTableNode* node = tempNodeStack.top();
				tempNodeStack.pop();
				tempNodeList.push_back(node);
			}
			for (int i = (int) tempNodeList.size() - 1; i >= 0; i--) {
				const ResultGraphTableNode* node = tempNodeList.at(i);
				cout << node->getNodeIdentifier() << " ";
			}
			cout << endl;*/ 

			// check if the node is a node of synonym2
			const std::string& currentNodeSynonymName = currentNode->getSynonymName();
			if (currentNodeSynonymName != synonym2) {
				// currentNode is not a node of synonym
				//		then if the currentNode has not been visited before, 
				//			we add all the edges of the node which are not for the synonym of name prevSynonymName. 
				//			if no edges are added, then edgesToDestroyTemp must be popped
				//			off until it is empty (because this is a leaf*) or the top edge has one of its nodes the same as one of the nodes in the next edge we
				//			will traverse.
				//		if the currentNode has been visited before but relationshipTruthMap is false,
				//			then we pop off from edgesToDestroyTemp
				//			until it is empty or the top edge has one of its nodes the same as one of the nodes in the next edge we 
				//			will traverse. Add all the popped edges into the edgesToDestroy set
				//		else if the currentNode has been visited before and relationshipTruthMap is true,
				//			then we pop off ALL edges from edgesToDestroyTemp into edgesToSave
				const std::string& currentId = currentNode->getNodeIdentifier();
				//if ( !Utilities::isKeyInMap_TypeType(nodeVisitedMap, currentId)) {
				const std::string& nextNodeSynonymName = pathMap.at(currentNodeSynonymName);
				currentEdges = getEdgesOfNode(*currentNode, nextNodeSynonymName);
				for (auto it = currentEdges->begin(); it != currentEdges->end(); it++) {
					const edge *e = &it->second;
					//cout << "DEBUGGING: Pushed edge: " << getEdgeIdentifier(*e) << endl;
					edgesStack.push(e);
				}
				// Mark currentNode as visited because edges have been added to the stack
				nodeVisitedMap.insert(std::make_pair(currentId, true));
							
					//if ( !wasEdgeAdded) {
					//	// no edge was added
					//	//		edgesToDestroyTemp must be popped
					//	//		off until it is empty (because this is a leaf*) 
					//	//		or the top edge has one of its nodes the same as one of the nodes in the next edge we
					//	//		will traverse.
					//	cout << "Shouldn't have reached the case when this is a leaf!\n";
					//	if ( !edgesStack.empty()) {
					//		// there are more edges to traverse
					//		// otherwise there would be no need to do anything because there are no more traversals to be done
					//		const edge& nextEdgeToTraverse = edgesStack.top();
					//		popEdgesIntoUnorderedMapUntilSimilarNodeReached(&edgesToDestroyTemp, new EdgeMap(), nextEdgeToTraverse);
					//		currentNode = popNodesUntilSimillarNodeReached(&nodeStack, nextEdgeToTraverse);
					//	}
					//}
				//} else {
				//	// Node visited before!
				//	// Use the value stored in nodeVisitedMap!
				//	bool isRelationshipTrue = nodeVisitedMap.at(currentId);

				//	std::vector<edge> *poppedEdges = NULL;
				//	if (isRelationshipTrue) {
				//		// Relationship is true, so pop the edges to save
				//		poppedEdges = &popAllEdgesIntoUnorderedMap(&edgesToDestroyTemp, edgesToSave);
				//		if ( !edgesStack.empty()) {
				//			// There is another edge to traverse, so we need to get the currentNode to start from there
				//			const edge *nextEdgeToTraverse = edgesStack.top();
				//			currentNode = popNodesUntilSimillarNodeReached(&nodeStack, *nextEdgeToTraverse);
				//		}
				//	} else {
				//		// Relationship is false, so pop the edges to delete, up until the next edge to traverse
				//		if ( !edgesStack.empty()) {
				//			// There is another edge to traverse, so we need to get the currentNode to start from there
				//			const edge *nextEdgeToTraverse = edgesStack.top();
				//			poppedEdges = &popEdgesIntoUnorderedMapUntilSimilarNodeReached(&edgesToDestroyTemp, edgesToDestroy, *nextEdgeToTraverse);
				//			currentNode = popNodesUntilSimillarNodeReached(&nodeStack, *nextEdgeToTraverse);
				//		} else {
				//			// There are no more edges, just pop all the edges to destroy
				//			poppedEdges = &popAllEdgesIntoUnorderedMap(&edgesToDestroyTemp, edgesToDestroy);
				//		}

				//		// Store the bad (popped) edges into mBadEdgesMapPtr for use during tuple finding
				//		// Ensure that there is a BadEdgeMap for startingNode and for currentNode
				//		const std::string& startingNodeId = startingNode->getNodeIdentifier();
				//		if ( !Utilities::isKeyInMap_TypeType(mBadEdgeMapPtrs, startingNodeId)) {
				//			mBadEdgeMapPtrs[startingNodeId] = new BadEdgeMap();
				//		}
				//		if ( !Utilities::isKeyInMap_TypeType(mBadEdgeMapPtrs, currentId)) {
				//			mBadEdgeMapPtrs[currentId] = new BadEdgeMap();
				//		}
				//		BadEdgeMap *badEdgeMapStart = mBadEdgeMapPtrs[startingNodeId];
				//		BadEdgeMap *badEdgeMapCurrent = mBadEdgeMapPtrs[currentId];
				//		for (unsigned int i = 0; i < poppedEdges->size(); i++) {
				//			const edge& e = poppedEdges->at(i);
				//			//cout << "Bad edge for " << startingNodeId << " and " << currentNodeId
				//			//	<< " is " << getEdgeIdentifier(e) << '\n';
				//			badEdgeMapStart->insert( std::make_pair(getEdgeIdentifier(e), true) );
				//			badEdgeMapCurrent->insert( std::make_pair(getEdgeIdentifier(e), true) );
				//		}
				//	}

				//	// Store the relationship (true/false) in the nodeVisitedMap so that if we reach this node again,
				//	// we can look up this table to decide what to do immediately without traversing the other edges
				//	for (unsigned int i = 0; i < poppedEdges->size(); i++) {
				//		const edge& e = poppedEdges->at(i);
				//		const std::string& leftId = e.leftNode->getNodeIdentifier();
				//		const std::string& rightId = e.rightNode->getNodeIdentifier();
				//		if (isRelationshipTrue) {
				//			// When a relationship is true, always overwrite
				//			nodeVisitedMap[leftId] = true;
				//			nodeVisitedMap[rightId] = true;
				//		} else {
				//			// When a relationship is false, don't overwrite, only insert
				//			nodeVisitedMap.insert( std::make_pair(leftId, false) );
				//			nodeVisitedMap.insert( std::make_pair(rightId, false) );
				//		}
				//	}
				//}
			} else {
				// currentNode is a node of synonym2
				//		then we do not add any edges of the node, but instead check if the relationship is true.
				//		if it is,
				//			then we pop off ALL edges from edgesToDestroyTemp into a edgesToSave set.
				//		if it is not, 
				//			then we pop off from edgesToDestroyTemp
				//			until it is empty or the top edge has one of its nodes the same as one of the nodes in the next edge we 
				//			will traverse. Add all the popped edges into the edgesToDestroy set. 
				int synonym1Value = startingNode->getNodeValue();
				int synonym2Value = currentNode->getNodeValue();
				DesignEntityType synonym1Type = synonymTable->getDesignEntityType(synonym1);
				DesignEntityType synonym2Type = synonymTable->getDesignEntityType(synonym2);
				const std::string &currentId = currentNode->getNodeIdentifier();

				bool isRelationshipTrue;
				if (Utilities::isKeyInMap_TypeType(nodeVisitedMap, currentId)) {
					// Use the stored result if already visited
					isRelationshipTrue = nodeVisitedMap.at(currentId);
				} else if (isTimeConsumingRelType) {
					isRelationshipTrue = Utilities::isKeyInMap_TypeType(*synonym2TrueIndexesMap, synonym2Value);
				} else {
					isRelationshipTrue = checkIfIsTrueRelationship(pkb, relType, synonym1Value, synonym2Value, synonym1Type, synonym2Type);
				}
				
				std::vector<edge> *poppedEdges = NULL;
				if (isRelationshipTrue) {
					// Relationship is true, so pop the edges to save
					poppedEdges = &popAllEdgesIntoUnorderedMap(&edgesToDestroyTemp, edgesToSave);
					std::stack<const ResultGraphTableNode*> nodeStackCopy = nodeStack;
					if ( !edgesStack.empty()) { 
						// There is another edge to traverse, so we need to get the currentNode to start from there
						const edge *nextEdgeToTraverse = edgesStack.top();
						currentNode = popNodesUntilSimillarNodeReached(&nodeStack, *nextEdgeToTraverse);
					}
					// Store the good (popped) edges into mBadEdgesMapPtr for use during tuple finding
					// Ensure that there is a BadEdgeMap for startingNode and for currentNode
					while ( !nodeStackCopy.empty()) {
						const ResultGraphTableNode *node = nodeStackCopy.top();
						nodeStackCopy.pop();

						const std::string& nodeId = node->getNodeIdentifier();
						if ( !Utilities::isKeyInMap_TypeType(mGoodEdgeMapPtrs, nodeId)) {
							mGoodEdgeMapPtrs[nodeId] = new BadEdgeMap();
						}
						BadEdgeMap *goodEdgeMap = mGoodEdgeMapPtrs[nodeId];

						for (unsigned int i = 0; i < poppedEdges->size(); i++) {
							const edge& e = poppedEdges->at(i);
							const std::string &edgeId = getEdgeIdentifier(e);
							if ( !Utilities::isKeyInMap_TypeType(*goodEdgeMap, edgeId)) {
								goodEdgeMap->insert( std::make_pair(edgeId, true) );
							}
						}
					}
					
				} else {
					// Relationship is false, so pop the edges to delete, up until the next edge to traverse
					if ( !edgesStack.empty()) {
						// There is another edge to traverse, so we need to get the currentNode to start from there
						const edge *nextEdgeToTraverse = edgesStack.top();
						poppedEdges = &popEdgesIntoUnorderedMapUntilSimilarNodeReached(&edgesToDestroyTemp, edgesToDestroy, *nextEdgeToTraverse);
						currentNode = popNodesUntilSimillarNodeReached(&nodeStack, *nextEdgeToTraverse);
					} else {
						// There are no more edges, just pop all the edges to destroy
						poppedEdges = &popAllEdgesIntoUnorderedMap(&edgesToDestroyTemp, edgesToDestroy);
					}

					// Store the bad (popped) edges into mBadEdgesMapPtr for use during tuple finding
					// Ensure that there is a BadEdgeMap for startingNode and for currentNode
					const std::string& startingNodeId = startingNode->getNodeIdentifier();
					if ( !Utilities::isKeyInMap_TypeType(mBadEdgeMapPtrs, startingNodeId)) {
						mBadEdgeMapPtrs[startingNodeId] = new BadEdgeMap();
					}
					if ( !Utilities::isKeyInMap_TypeType(mBadEdgeMapPtrs, currentId)) {
						mBadEdgeMapPtrs[currentId] = new BadEdgeMap();
					}
					BadEdgeMap *badEdgeMapStart = mBadEdgeMapPtrs[startingNodeId];
					BadEdgeMap *badEdgeMapCurrent = mBadEdgeMapPtrs[currentId];
					for (unsigned int i = 0; i < poppedEdges->size(); i++) {
						const edge& e = poppedEdges->at(i);
						const std::string &edgeId = getEdgeIdentifier(e);

						//cout << "Bad edge for " << startingNodeId << " and " << currentNodeId
						//	<< " is " << getEdgeIdentifier(e) << '\n';
						if ( !Utilities::isKeyInMap_TypeType(*badEdgeMapStart, edgeId)) {
							badEdgeMapStart->insert( std::make_pair(edgeId, true) );
						}
						if ( !Utilities::isKeyInMap_TypeType(*badEdgeMapCurrent, edgeId)) {
							badEdgeMapCurrent->insert( std::make_pair(edgeId, true) );
						}

						const ResultGraphTableNode *leftNode = e.leftNode;
						const ResultGraphTableNode *righttNode = e.rightNode;
						const std::string& leftNodeId = leftNode->getNodeIdentifier();
						const std::string& rightNodeId = rightNode->getNodeIdentifier();
						if ( !Utilities::isKeyInMap_TypeType(mBadEdgeMapPtrs, leftNodeId)) {
							mBadEdgeMapPtrs[leftNodeId] = new BadEdgeMap();
						}
						if ( !Utilities::isKeyInMap_TypeType(mBadEdgeMapPtrs, rightNodeId)) {
							mBadEdgeMapPtrs[rightNodeId] = new BadEdgeMap();
						}
						BadEdgeMap *badEdgeMapLeft = mBadEdgeMapPtrs[leftNodeId];
						BadEdgeMap *badEdgeMapRight = mBadEdgeMapPtrs[rightNodeId];
						if ( !Utilities::isKeyInMap_TypeType(*badEdgeMapLeft, edgeId)) {
							badEdgeMapLeft->insert( std::make_pair(edgeId, true) );
						}
						if ( !Utilities::isKeyInMap_TypeType(*badEdgeMapRight, edgeId)) {
							badEdgeMapRight->insert( std::make_pair(edgeId, true) );
						}
					}
				}

				// Store the relationship (true/false) in the nodeVisitedMap so that if we reach this node again,
				// we can look up this table to decide what to do immediately without traversing the other edges
				for (auto it = poppedEdges->begin(); it != poppedEdges->end(); it++) {
					const edge& e = *it;
					const std::string& leftId = e.leftNode->getNodeIdentifier();
					const std::string& rightId = e.rightNode->getNodeIdentifier();
					if (isRelationshipTrue) {
						// When a relationship is true, always overwrite
						nodeVisitedMap[leftId] = true;
						nodeVisitedMap[rightId] = true;
					} else {
						// When a relationship is false, don't overwrite, only insert
						if ( !Utilities::isKeyInMap_TypeType(nodeVisitedMap, leftId)) {
							nodeVisitedMap.insert( std::make_pair(leftId, false) );
						}
						if ( !Utilities::isKeyInMap_TypeType(nodeVisitedMap, rightId)) {
							nodeVisitedMap.insert( std::make_pair(rightId, false) );
						}
					}
				}
			}
		}	
}

// Finds all synonym1 nodes that do NOT have a DIRECT link to a synonym2 node and deletes them and their edges.
// After deleting a node, this function also traverses all the deleted edges, attempting to find nodes which are not even indirectly
// linked to a synonym2 node. If such nodes are found, these nodes and their edges are also deleted, and this is done recursively
// until no more such nodes are found.
void ResultGraphTable::ensureDirectLinkRemainOnly(const std::string& synonym1, const std::string& synonym2) {
	if ( !isSynonymInTable(synonym1)) {
		cout << "Error ensureDirectLinkRemainOnly(): synonym1 not in the table!\n";
	}
	if ( !isSynonymInTable(synonym2)) {
		cout << "Error ensureDirectLinkRemainOnly(): synonym2 not in the table!\n";
	}

	std::vector<ResultGraphTableNode> nodesToDelete;
	NodeMap* nodeColumn1 = mColumns.at(synonym1);
	for (auto it = nodeColumn1->begin(); it != nodeColumn1->end(); it++) {
		const ResultGraphTableNode* node = it->second;
		if (getCountOfAdjacentNodeOfSynonymName(*node, synonym2) <= 0) {
			nodesToDelete.push_back(*node);
		}
	}
	for (unsigned int i = 0; i < nodesToDelete.size(); i++) {
		destroyEdges(*(getEdgesOfNode(nodesToDelete.at(i), ANY_SYNONYM)));
	}
	for (unsigned int i = 0; i < nodesToDelete.size(); i++) {
		deleteNode(nodesToDelete.at(i));
	}
}

bool ResultGraphTable::isSynonymRelatedToSynonym(const std::string& synonym1, const std::string& synonym2) {
	PathMap& pathMap = findPathFromSynonymToSynonym(synonym1, synonym2);
	if (pathMap.size() == 0) {
		return false;
	} else {
		return true;
	}
}

// Finds a path from synonym1 to synonym2 in the graph if there exists one.
// Returns the path in a unordered_map<currentSynonym, nextSynonymToGoTo> format, which
// tells you which synonym to go to next if you are at currentSynonym.
// Returns a size 0 unordered_map if there is no path to get from synonym1 to synonym2.
ResultGraphTable::PathMap& ResultGraphTable::findPathFromSynonymToSynonym(const std::string& synonym1, const std::string& synonym2) {
	PathMap* pathMap = new PathMap();
	if ( !isSynonymInTable(synonym1) || !isSynonymInTable(synonym2)) {
		// Immediately return the empty pathMap when either of the synonyms are not in the table
		return *pathMap;
	}

	if (synonym1 == synonym2) {
		// Path to itself is.. just itself to itself.
		pathMap->insert( std::pair<std::string, std::string>(synonym1, synonym1) );
		return *pathMap;
	}

	const ResultGraphTableNode *headerNode1 = mHeaders.at(synonym1);

	// Depth-first traverse from the headerNode1 until we have traversed everything or we have reached a headerNode with synonymName == synonym2
	std::unordered_map<std::string, bool> nodeVisitedMap;
	std::unordered_map<std::string, bool> edgeAddedMap;
	std::stack<ResultGraphTable::edge> edgesStack;
	const ResultGraphTableNode *currentNode = headerNode1;
	// Place all edges of the current node onto the stack if it has not yet been visited
	if ( !isNodeInMap(nodeVisitedMap, currentNode)) {
		EdgeMap* currentEdges = getEdgesOfNode(*currentNode, ANY_SYNONYM);
		for (auto it = currentEdges->begin(); it != currentEdges->end(); it++) {
			const edge& e = it->second;
			edgesStack.push(e);
			edgeAddedMap.insert( std::pair<std::string, bool>(getEdgeIdentifier(e), true) );
		}
		nodeVisitedMap.insert(std::pair<std::string, bool>(currentNode->getNodeIdentifier(), true));
	}

	// keep track of the stack of nodes as we traverse
	std::stack<const ResultGraphTableNode*> nodeStack;
	nodeStack.push(currentNode);

	while ( !edgesStack.empty()) {

		// Pop an edge from the stack to traverse
		const edge& currentEdge = edgesStack.top();
		edgesStack.pop();

		const ResultGraphTableNode *leftNode = currentEdge.leftNode;
		const ResultGraphTableNode *rightNode = currentEdge.rightNode;
		const std::string& currentNodeSynonymName = currentNode->getSynonymName();

		if (leftNode->getSynonymName() == currentNodeSynonymName) {
			// The rightNode is the correct one to traverse
			currentNode = rightNode;
		} else {
			// The leftNode is the correct one to traverse
			currentNode = leftNode;
		}
		
		if ( !isNodeInMap(nodeVisitedMap, currentNode)) {
			nodeStack.push(currentNode);
		}

		if (currentNode->getSynonymName() == synonym2) {
			// We have found the path from synonym1 to synonym2!
			// The nodeStack contains our path!
			// The top of the stack is synonym2, and the bottom of the stack is synonym1.
			// There must be at least 2 nodes, the start and the end!
			// Even if the start node is the end node, it should be in here!
			if (nodeStack.size() < 2) {
				cout << "Error in findPathFromSynonymToSynonym()! pathSize have only " << nodeStack.size() << " nodes! (less than 2)\n";
			}
			// Now, put it all into the pathMap
			//cout << "Path from " << synonym1 << " to " << synonym2 << "\n";
			while ( nodeStack.size() > 1) {
				const std::string& nextSynonymName = nodeStack.top()->getSynonymName();
				nodeStack.pop();
				const std::string& currentSynonymName = nodeStack.top()->getSynonymName();
				//cout << nextSynonymName << " <- " << currentSynonymName << "\n";
				pathMap->insert( std::pair<string, string>(currentSynonymName, nextSynonymName) );
			}
			
			return *pathMap;
		}

		// Place all edges of the current node onto the stack if it has not yet been visited
		// and the edge has not been added before
		if ( !isNodeInMap(nodeVisitedMap, currentNode)) {
			EdgeMap* currentEdges = getEdgesOfNode(*currentNode, ANY_SYNONYM);
			bool wasEdgeAdded = false;
			for (auto it = currentEdges->begin(); it != currentEdges->end(); it++) {
				const edge& e = it->second;
				if ( !Utilities::isKeyInMap_TypeType(edgeAddedMap, getEdgeIdentifier(e))) {
					edgesStack.push(e);
					edgeAddedMap.insert( std::pair<std::string, bool>(getEdgeIdentifier(e), true) );
					wasEdgeAdded = true;
				}
			}
			nodeVisitedMap.insert(std::pair<std::string, bool>(currentNode->getNodeIdentifier(), true));
			if ( !wasEdgeAdded) {
				// Going to backtrack, so pop nodes until the next node to traverse from
				if (edgesStack.size() != 0) {
					const edge& nextEdgeToTraverse = edgesStack.top();
					// End of depth-first traversal, so we have to back off and pop nodes until the correct one
					currentNode = popNodesUntilSimillarNodeReached(&nodeStack, nextEdgeToTraverse);
				}
			}
		}
	} while ( !edgesStack.empty());

	// If we exited the above loop, we never found a node of synonym2 from traversing the edges from synonym1 headerNode
	// so return the empty pathMap
	return *pathMap;
}
	

// Initializes the column for synonymName if it doesn't already exist, and returns the pointer to the header node
const ResultGraphTableNode& ResultGraphTable::initializeColumn(const std::string& synonymName) {
	if (!isSynonymInTable(synonymName)) {
		ResultGraphTableNode *headerNode = new ResultGraphTableNode(synonymName);
		// Insert into mHeaders the headerNode, indexed with synonymName
		mHeaders.insert(std::pair<std::string, ResultGraphTableNode*>(synonymName, headerNode));
		// Insert into mColumns an empty list of nodes, indexed with synonymName
		mColumns.insert(std::pair<std::string, NodeMap*>(synonymName, new NodeMap()));
	}
	return *(mHeaders.at(synonymName));
}

// Creates an edge between the 2 specified nodes and places that edge in the list of edges for the 2 nodes in mEdges
void ResultGraphTable::linkNodes(const ResultGraphTableNode& node1, const ResultGraphTableNode& node2) {
	edge e;
	e.leftNode = &node1;
	e.rightNode = &node2;

	const std::string& node1Id = node1.getNodeIdentifier();
	const std::string& node2Id = node2.getNodeIdentifier();
	
	if ( !Utilities::isKeyInMap_TypeType(mEdges, node1Id)) {
		mEdges.insert( std::make_pair(node1Id, new EdgeMapsBySynonymName()) );
	}
	if ( !Utilities::isKeyInMap_TypeType(mEdges, node2Id)) {
		mEdges.insert( std::make_pair(node2Id, new EdgeMapsBySynonymName()) );
	}

	EdgeMapsBySynonymName* edgeMapsOfNode1 = mEdges.at(node1Id);
	EdgeMapsBySynonymName* edgeMapsOfNode2 = mEdges.at(node2Id);
	const std::string& edgeId = getEdgeIdentifier(e);
	const std::string& node1Synonym = node1.getSynonymName();
	const std::string& node2Synonym = node2.getSynonymName();

	if ( !Utilities::isKeyInMap_TypeType(*edgeMapsOfNode1, node2Synonym)) {
		edgeMapsOfNode1->insert( std::make_pair(node2Synonym, new EdgeMap()) );
	}
	if ( !Utilities::isKeyInMap_TypeType(*edgeMapsOfNode2, node1Synonym)) {
		edgeMapsOfNode2->insert( std::make_pair(node1Synonym, new EdgeMap()) );
	}
	if ( !Utilities::isKeyInMap_TypeType(*edgeMapsOfNode1, ANY_SYNONYM)) {
		edgeMapsOfNode1->insert( std::make_pair(ANY_SYNONYM, new EdgeMap()) );
	}
	if ( !Utilities::isKeyInMap_TypeType(*edgeMapsOfNode2, ANY_SYNONYM)) {
		edgeMapsOfNode2->insert( std::make_pair(ANY_SYNONYM, new EdgeMap()) );
	}
	EdgeMap *edgesOfNode1 = edgeMapsOfNode1->at(node2Synonym);
	EdgeMap *edgesOfNode2 = edgeMapsOfNode2->at(node1Synonym);
	EdgeMap *anyEdgesOfNode1 = edgeMapsOfNode1->at(ANY_SYNONYM);
	EdgeMap *anyEdgesOfNode2 = edgeMapsOfNode2->at(ANY_SYNONYM);

	if (Utilities::isKeyInMap_TypeType(*edgesOfNode1, edgeId)) {
		// Linked these nodes before, so exit!
		return;
	}
	edgesOfNode1->insert( std::make_pair(edgeId, e) );
	edgesOfNode2->insert( std::make_pair(edgeId, e) );
	anyEdgesOfNode1->insert( std::make_pair(edgeId, e) );
	anyEdgesOfNode2->insert( std::make_pair(edgeId, e) );

	// Maintain the mAdjacentNodeCountMap
	if ( !Utilities::isKeyInMap_TypeType(mAdjacentNodeCountMap, node1Id)) {
		// Doesn't have node1's identifier in the unordered_map, so we insert it in
		mAdjacentNodeCountMap.insert(std::pair<std::string, NodeCountMap*>(node1Id, new NodeCountMap()));
	}
	if ( !Utilities::isKeyInMap_TypeType(mAdjacentNodeCountMap, node2Id)) {
		// Doesn't have node2's identifier in the unordered_map, so we insert it in
		mAdjacentNodeCountMap.insert(std::pair<std::string, NodeCountMap*>(node2Id, new NodeCountMap()));
	}
	NodeCountMap* nodeCountMap1 = mAdjacentNodeCountMap.at(node1Id);
	NodeCountMap* nodeCountMap2 = mAdjacentNodeCountMap.at(node2Id);
	if ( !Utilities::isKeyInMap_TypeType(*nodeCountMap1, node2Synonym)) {
		// Doesn't have synonymName2 in the unordered_map, so we insert it in
		nodeCountMap1->insert(std::pair<std::string, int>(node2Synonym, 0));
	}
	if ( !Utilities::isKeyInMap_TypeType(*nodeCountMap2, node1Synonym)) {
		// Doesn't have synonymName2 in the unordered_map, so we insert it in
		nodeCountMap2->insert(std::pair<std::string, int>(node1Synonym, 0));
	}

	// Increase the count by 1
	nodeCountMap1->at(node2Synonym)++;
	nodeCountMap2->at(node1Synonym)++;

	// Maintain the mAdjacentEdgeCountMap
	if ( !Utilities::isKeyInMap_TypeType(mAdjacentEdgeCountMap, node1Synonym)) {
		// Doesn't have synonym1 in the unordered_map, so we insert it in
		mAdjacentEdgeCountMap.insert( std::make_pair(node1Synonym, new EdgeCountMap()) );
	}
	if ( !Utilities::isKeyInMap_TypeType(mAdjacentEdgeCountMap, node2Synonym)) {
		// Doesn't have synonym2 in the unordered_map, so we insert it in
		mAdjacentEdgeCountMap.insert( std::make_pair(node2Synonym, new EdgeCountMap()) );
	}

	EdgeCountMap* edgeCountMap1 = mAdjacentEdgeCountMap.at(node1Synonym);
	EdgeCountMap* edgeCountMap2 = mAdjacentEdgeCountMap.at(node2Synonym);
	if ( !Utilities::isKeyInMap_TypeType(*edgeCountMap1, node2Synonym)) {
		// Doesn't have synonymName2 in the unordered_map, so we insert it in
		edgeCountMap1->insert( std::make_pair(node2Synonym, 0) );
	}
	if ( !Utilities::isKeyInMap_TypeType(*edgeCountMap2, node1Synonym)) {
		// Doesn't have synonymName1 in the unordered_map, so we insert it in
		edgeCountMap2->insert( std::make_pair(node1Synonym, 0) );
	}

	// Increase the count by 1
	edgeCountMap1->at(node2Synonym)++;
	edgeCountMap2->at(node1Synonym)++;
}

// Finds out if, using the pkb, the relationship of relType is true between the given synonym1Value and synonym2Value
bool ResultGraphTable::checkIfIsTrueRelationship(PKB *pkb, RelationshipType relType, int synonym1Value, int synonym2Value,
	DesignEntityType synonym1Type, DesignEntityType synonym2Type) {

		bool isRelationshipTrue = true;
		
		std::string synonym1NameValue, synonym2NameValue;
		switch (relType) {
		case MODIFIES_LINE:
			isRelationshipTrue = pkb->isLineModifies(synonym1Value, synonym2Value);
			break;
		case MODIFIES_PROC:
			isRelationshipTrue = pkb->isProcModifies(synonym1Value, synonym2Value);
			break;
		case USES_LINE:
			isRelationshipTrue = pkb->isLineUses(synonym1Value, synonym2Value);
			break;
		case USES_PROC:
			isRelationshipTrue = pkb->isProcUses(synonym1Value, synonym2Value);
			break;
		case PARENT:
			isRelationshipTrue = pkb->isParent(synonym1Value, synonym2Value);
			break;
		case PARENT_STAR:
			isRelationshipTrue = pkb->isParentStar(synonym1Value, synonym2Value);
			break;
		case FOLLOWS:
			isRelationshipTrue = pkb->isFollows(synonym1Value, synonym2Value);
			break;
		case FOLLOWS_STAR:
			isRelationshipTrue = pkb->isFollowStar(synonym1Value, synonym2Value);
			break;
		case CALLS:
			isRelationshipTrue = pkb->isCalls(synonym1Value, synonym2Value);
			break;
		case CALLS_STAR:
			isRelationshipTrue = pkb->isCallsStar(synonym1Value, synonym2Value);
			break;
		case NEXT:
			isRelationshipTrue = pkb->isNext(synonym1Value, synonym2Value);
			break;
		case NEXT_STAR:
			isRelationshipTrue = pkb->isNextStar(synonym1Value, synonym2Value);
			break;
		case NEXTBIP:
			isRelationshipTrue = pkb->isNextBip(synonym1Value, synonym2Value);
			break;
		case NEXTBIP_STAR:
			isRelationshipTrue = pkb->isNextBipStar(synonym1Value, synonym2Value);
			break;
		case AFFECTS:
			isRelationshipTrue = pkb->isAffects(synonym1Value, synonym2Value);
			break;
		case AFFECTS_STAR:
			isRelationshipTrue = pkb->isAffectsStar(synonym1Value, synonym2Value);
			break;
		case AFFECTSBIP:
			isRelationshipTrue = pkb->isAffectBip(synonym1Value, synonym2Value);
			break;
		case AFFECTSBIP_STAR:
			isRelationshipTrue = pkb->isAffectBipStar(synonym1Value, synonym2Value);
			break;
		case EQUALS_NAME:
			// Need to convert the synonym1Value and synonym2Value into their corresponding names using the PKB and their synonym types,
			// and compare to see if the names are equal
			switch (synonym1Type) {
			case VARIABLE:
				synonym1NameValue = pkb->getVarName(synonym1Value);
				break;
			case PROCEDURE:
				synonym1NameValue = pkb->getProcName(synonym1Value);
				break;
			case CALL:
				synonym1NameValue = pkb->getProcName(pkb->getCalledByLine(synonym1Value));
				break;
			default:
				// Shouldn't be here because only variables and procedures have names
				cout << "Error in ResultGraphTable checkIfIsTrueRelationship(): In a conditional branch we shouldn't be in!\n";
				return false;
			}

			switch (synonym2Type) {
			case VARIABLE:
				synonym2NameValue = pkb->getVarName(synonym2Value);
				break;
			case PROCEDURE:
				synonym2NameValue = pkb->getProcName(synonym2Value);
				break;
			case CALL:
				synonym2NameValue = pkb->getProcName(pkb->getCalledByLine(synonym2Value));
				break;
			default:
				// Shouldn't be here because only variables and procedures have names
				cout << "Error in ResultGraphTable checkIfIsTrueRelationship(): In a conditional branch we shouldn't be in!\n";
				return false;
			}

			isRelationshipTrue = (synonym1NameValue == synonym2NameValue);
			break;
		case EQUALS_INDEX:
			// Only need to compare the indexes to see if they are equal
			isRelationshipTrue = (synonym1Value == synonym2Value);
			break;
		case CONTROL_VARIABLE:
			isRelationshipTrue = pkb->getNodeByLine(synonym1Value)->getChild().at(0)->getContent() == synonym2Value;
			break;
		default:
			// Currently invalid relType
			cout << "Error in ResultGraphTable checkIfIsTrueRelationship(): trying to evaluate a currently invalid relType -> " << relType << "\n";
			isRelationshipTrue = false;
			break;
		}

		return isRelationshipTrue;
}

// Finds, using the pkb, and returns ALL the relationship pairs for the relationship relType between synonyms 1 and 2
std::vector<std::pair<int, std::vector<int>>>& ResultGraphTable::getAllTrueRelationshipPairs(PKB *pkb, SynonymTable *synonymTable, 
	RelationshipType relType, const std::string& synonym1, const std::string& synonym2) {
		
		std::clock_t start;
		double duration;

		start = std::clock(); // time how long getAllTrueRelationshipPairs() takes

		std::vector<std::pair<int, std::vector<int>>> *trueRelationshipPairs = new std::vector<std::pair<int, std::vector<int>>>();

		// Currently, all synonym1 are lines
		DesignEntityType synonym1EntityType = synonymTable->getDesignEntityType(synonym1);
		std::vector<int>& synonym1Indexes = getAllIndexes(synonym1EntityType, pkb);

		for (unsigned int i = 0; i < synonym1Indexes.size(); i++) {
			int synonym1Index = synonym1Indexes.at(i);
			std::vector<int>& synonym2TrueIndexes = getTrueRelationshipSynonym2IndexesForGivenSynonym1Index(pkb,
																											synonymTable,
																											relType,
																											synonym1,
																											synonym2,
																											synonym1Index);

			if (synonym1 == synonym2) {
				leaveOnlyEqualIndexes(&synonym2TrueIndexes, synonym1Index);
			}

			if (synonym2TrueIndexes.size() > 0) {
				trueRelationshipPairs->push_back(std::pair<int, std::vector<int>>(synonym1Index, synonym2TrueIndexes));
			}
		}
		
		duration = ( std::clock() - start ) / (double) CLOCKS_PER_SEC;
		//cout << "getAllTrueRelationshipPairs() for relType " << relType << " took " << duration << " seconds\n";
		return *trueRelationshipPairs;
}

// Finds, using the pkb, and returns ALL the indexes of synonym2 for the relationship relType between 
// the specified index synonym1Value of synonym 1 and all of synonym2
std::vector<int>& ResultGraphTable::getTrueRelationshipSynonym2IndexesForGivenSynonym1Index(PKB *pkb, SynonymTable *synonymTable, RelationshipType relType, 
	const std::string& synonym1, const std::string& synonym2, int synonym1Value) {

		/*if ( (synonym1 == synonym2) && (relType == MODIFIES_LINE || relType == MODIFIES_PROC || relType == USES_LINE || relType == USES_PROC
			|| relType == PARENT || relType == PARENT_STAR || relType == FOLLOWS || relType == FOLLOWS_STAR || relType == CALLS
			|| relType == CALLS_STAR || relType == NEXT)) {
				return std::vector<int>();
		}*/

		std::vector<int> *syn2IndexesForGivenSyn1Index = new std::vector<int>();
		DesignEntityType synonym2EntityType = synonymTable->getDesignEntityType(synonym2);

		DesignEntityType synonym1Type;
		DesignEntityType synonym2Type;
		std::vector<int> *synonym2Values = NULL;
		int syn2Index;
		switch (relType) {
		case MODIFIES_LINE:
			*syn2IndexesForGivenSyn1Index = pkb->getModifiedVarsByLine(synonym1Value);
			break;
		case MODIFIES_PROC:
			*syn2IndexesForGivenSyn1Index = pkb->getModifiedVarsByProc(synonym1Value);
			break;
		case USES_LINE:
			*syn2IndexesForGivenSyn1Index = pkb->getUsedVarsByLine(synonym1Value);
			break;
		case USES_PROC:
			*syn2IndexesForGivenSyn1Index = pkb->getUsedVarsByProc(synonym1Value);
			break;
		case PARENT:
			*syn2IndexesForGivenSyn1Index = pkb->getChild(synonym1Value);
			break;
		case PARENT_STAR:
			*syn2IndexesForGivenSyn1Index = pkb->getChildStar(synonym1Value);
			break;
		case FOLLOWS:
			syn2Index = pkb->getFollows(synonym1Value);
			// if syn2Index <= 0 then there is no line that follows synonym1Value
			if (syn2Index > 0) {
				syn2IndexesForGivenSyn1Index->push_back(syn2Index);
			}
			break;
		case FOLLOWS_STAR:
			*syn2IndexesForGivenSyn1Index = pkb->getFollowStar(synonym1Value);
			break;
		case CALLS:
			*syn2IndexesForGivenSyn1Index = pkb->getCalledBy(synonym1Value);
			break;
		case CALLS_STAR:
			*syn2IndexesForGivenSyn1Index = pkb->getCalledByStar(synonym1Value);
			break;
		case NEXT:
			*syn2IndexesForGivenSyn1Index = pkb->getSuccessorNext(synonym1Value);
			break;
		case NEXT_STAR:
			*syn2IndexesForGivenSyn1Index = pkb->getSuccessorNextStar(synonym1Value);
			break;
		case NEXTBIP:
			*syn2IndexesForGivenSyn1Index = pkb->getSuccessorNextBip(synonym1Value);
			break;
		case NEXTBIP_STAR:
			*syn2IndexesForGivenSyn1Index = pkb->getSuccessorNextBipStar(synonym1Value);
			break;
		case AFFECTS:
			*syn2IndexesForGivenSyn1Index = pkb->getAffected(synonym1Value);
			break;
		case AFFECTS_STAR:
			*syn2IndexesForGivenSyn1Index = pkb->getAffectedStar(synonym1Value);
			break;
		case AFFECTSBIP:
			*syn2IndexesForGivenSyn1Index = pkb->getAffectedBip(synonym1Value);
			break;
		case AFFECTSBIP_STAR:
			*syn2IndexesForGivenSyn1Index = pkb->getAffectedBipStar(synonym1Value);
			break;
		case EQUALS_NAME:
			synonym1Type = synonymTable->getDesignEntityType(synonym1);
			synonym2Type = synonymTable->getDesignEntityType(synonym2);

			syn2IndexesForGivenSyn1Index = &convertLeftSynonymIndexToRightSynonymIndex_VariableOrProcedureOrCall(synonym1Value, synonym1Type, synonym2Type, pkb);
			break;
		case EQUALS_INDEX:
			synonym2Type = synonymTable->getDesignEntityType(synonym2);

			// TODO optimize
			synonym2Values = &getAllIndexes(synonym2Type, pkb);
			for (unsigned int i = 0; i < synonym2Values->size(); i++) {
				int synonym2Value = synonym2Values->at(i);
				if (synonym2Value == synonym1Value) {
					syn2IndexesForGivenSyn1Index->push_back(synonym2Value);
				}
			}
			break;
		case CONTROL_VARIABLE:
			synonym2Type = synonymTable->getDesignEntityType(synonym2);

			// TODO optimize
			synonym2Values = &getAllIndexes(synonym2Type, pkb);
			for (unsigned int i = 0; i < synonym2Values->size(); i++) {
				int synonym2Value = synonym2Values->at(i);
				if (pkb->getNodeByLine(synonym1Value)->getChild().at(0)->getContent() == synonym2Value) {
					syn2IndexesForGivenSyn1Index->push_back(synonym2Value);
				}
			}
			break;
		default: 
			// Currently invalid relType
			cout << "Error in ResultGraphTable checkIfIsTrueRelationship(): trying to evaluate a currently invalid relType -> " << relType << "\n";
			*syn2IndexesForGivenSyn1Index = std::vector<int>();
			return *syn2IndexesForGivenSyn1Index;
			break;
		}

		// TODO remove this line and use PKB getXYZ(..., LineEntity) methods instead
		*syn2IndexesForGivenSyn1Index = validateIndexes(*syn2IndexesForGivenSyn1Index, synonym2EntityType, pkb);

		return *syn2IndexesForGivenSyn1Index;
}

// Finds, using the pkb, and returns ALL the indexes of synonym1 for the relationship relType between 
// all of synonym1 and the specified index synonym2Value
std::vector<int>& ResultGraphTable::getTrueRelationshipSynonym1IndexesForGivenSynonym2Index(PKB *pkb, SynonymTable *synonymTable, RelationshipType relType, 
	const std::string& synonym1, const std::string& synonym2, int synonym2Value) {

		std::vector<int> *syn1IndexesForGivenSyn2Index = new std::vector<int>();
		DesignEntityType synonym1EntityType = synonymTable->getDesignEntityType(synonym1);

		std::map<int, bool> syn1IndexesMap;

		DesignEntityType synonym1Type;
		DesignEntityType synonym2Type;
		std::vector<int> *synonym1Values = NULL;
		int syn1Index;
		switch (relType) {
		case MODIFIES_LINE:
			*syn1IndexesForGivenSyn2Index = pkb->getLinesModify(synonym2Value);
			break;
		case MODIFIES_PROC:
			*syn1IndexesForGivenSyn2Index = pkb->getProcsModify(synonym2Value);
			break;
		case USES_LINE:
			*syn1IndexesForGivenSyn2Index = pkb->getLinesUse(synonym2Value);
			break;
		case USES_PROC:
			*syn1IndexesForGivenSyn2Index = pkb->getProcsUse(synonym2Value);
			break;
		case PARENT:
			syn1Index = pkb->getParent(synonym2Value);
			// if syn1Index <= 0 then there is no line that is a parent of synonym2Value
			if (syn1Index > 0) {
				syn1IndexesForGivenSyn2Index->push_back(syn1Index);
			}
			break;
		case PARENT_STAR:
			*syn1IndexesForGivenSyn2Index = pkb->getParentStar(synonym2Value);
			break;
		case FOLLOWS:
			syn1Index = pkb->getFollowedBy(synonym2Value);
			// if syn1Index <= 0 then there is no line that is followed by synonym2Value
			if (syn1Index > 0) {
				syn1IndexesForGivenSyn2Index->push_back(syn1Index);
			}
			break;
		case FOLLOWS_STAR:
			*syn1IndexesForGivenSyn2Index = pkb->getFollowedByStar(synonym2Value);
			break;
		case CALLS:
			*syn1IndexesForGivenSyn2Index = pkb->getCallerOf(synonym2Value);
			break;
		case CALLS_STAR:
			*syn1IndexesForGivenSyn2Index = pkb->getCallerOfStar(synonym2Value);
			break;
		case NEXT:
			*syn1IndexesForGivenSyn2Index = pkb->getPredecessorNext(synonym2Value);
			break;
		case NEXT_STAR:
			*syn1IndexesForGivenSyn2Index = pkb->getPredecessorNextStar(synonym2Value);
			break;
		case NEXTBIP:
			*syn1IndexesForGivenSyn2Index = pkb->getPredecessorNextBip(synonym2Value);
			break;
		case NEXTBIP_STAR:
			*syn1IndexesForGivenSyn2Index = pkb->getPredecessorNextBipStar(synonym2Value);
			break;
		case AFFECTS:
			*syn1IndexesForGivenSyn2Index = pkb->getAffects(synonym2Value);
			break;
		case AFFECTS_STAR:
			*syn1IndexesForGivenSyn2Index = pkb->getAffectsStar(synonym2Value);
			break;
		case AFFECTSBIP:
			*syn1IndexesForGivenSyn2Index = pkb->getAffectBip(synonym2Value);
			break;
		case AFFECTSBIP_STAR:
			*syn1IndexesForGivenSyn2Index = pkb->getAffectBipStar(synonym2Value);
			break;
		case EQUALS_NAME:
			synonym1Type = synonymTable->getDesignEntityType(synonym1);
			synonym2Type = synonymTable->getDesignEntityType(synonym2);

			syn1IndexesForGivenSyn2Index = &convertLeftSynonymIndexToRightSynonymIndex_VariableOrProcedureOrCall(synonym2Value, synonym2Type, synonym1Type, pkb);
			break;
		case EQUALS_INDEX:
			synonym1Type = synonymTable->getDesignEntityType(synonym1);

			synonym1Values = &getAllIndexes(synonym1Type, pkb);
			for (unsigned int i = 0; i < synonym1Values->size(); i++) {
				int synonym1Value = synonym1Values->at(i);
				if (synonym1Value == synonym2Value) {
					syn1IndexesForGivenSyn2Index->push_back(synonym1Value);
				}
			}
			break;
		case CONTROL_VARIABLE:
			synonym1Type = synonymTable->getDesignEntityType(synonym1);

			synonym1Values = &getAllIndexes(synonym1Type, pkb);
			for (unsigned int i = 0; i < synonym1Values->size(); i++) {
				Type::Index::Line synonym1Value = synonym1Values->at(i);
				if ( !Utilities::isKeyInMap_TypeType(syn1IndexesMap, synonym2Value)
					&& (pkb->getNodeByLine(synonym1Value)->getChild().at(0)->getContent() == synonym2Value)) {
					syn1IndexesForGivenSyn2Index->push_back(synonym1Value);
					syn1IndexesMap.insert( std::make_pair(synonym1Value, true) );
				}
			}
			break;
		default: 
			// Currently invalid relType
			cout << "Error in ResultGraphTable checkIfIsTrueRelationship(): trying to evaluate a currently invalid relType -> " << relType << "\n";
			*syn1IndexesForGivenSyn2Index = std::vector<int>();
			return *syn1IndexesForGivenSyn2Index;
			break;
		}

		// TODO remove this line and use PKB getXYZ(..., LineEntity) methods instead
		*syn1IndexesForGivenSyn2Index = validateIndexes(*syn1IndexesForGivenSyn2Index, synonym1EntityType, pkb);
		
		return *syn1IndexesForGivenSyn2Index;
}

// Adds the resultNode if it isn't already present in the column of its synonymName
const ResultGraphTableNode* ResultGraphTable::addResultNodeUniquelyToColumn(const std::string& synonymName, int nodeValue) {
	if ( !isSynonymInTable(synonymName)) {
		// Shouldn't be adding to a column not yet created
		return NULL;
	}

	const std::string& nodeId = ResultGraphTableNode::getNodeIdentifier(synonymName, nodeValue);
	NodeMap* synonymColumn = mColumns.at(synonymName);
	if (Utilities::isKeyInMap_TypeType(*synonymColumn, nodeId)) {
		return synonymColumn->at(nodeId);
	} else {
		ResultGraphTableNode *resultNode = new ResultGraphTableNode(synonymName, nodeValue);
		synonymColumn->insert( std::pair<string, ResultGraphTableNode*>(nodeId, resultNode) );
		mColumns.at(synonymName) = synonymColumn;
		return resultNode;
	}
}

// Edge is identified by the string : (leftNodeId + rightNodeId)
std::string ResultGraphTable::getEdgeIdentifier(const edge& e) {
	return e.leftNode->getNodeIdentifier() + " " + e.rightNode->getNodeIdentifier();
}

// Get the list of edges of the specified node based on its node identifier and the synonym given, from mEdges
ResultGraphTable::EdgeMap* ResultGraphTable::getEdgesOfNode(const ResultGraphTableNode& node, const std::string &synonym) {
	const std::string& nodeId = node.getNodeIdentifier();
	if (Utilities::isKeyInMap_TypeType(mEdges, nodeId)) {
		EdgeMapsBySynonymName *edgeMaps = mEdges.at(nodeId);
		if (Utilities::isKeyInMap_TypeType(*edgeMaps, synonym)) {
			return edgeMaps->at(synonym);
		} else {
			return new EdgeMap();
		}
	} else {
		return new EdgeMap();
	}
}

bool ResultGraphTable::isNodeInMap(const std::unordered_map<std::string, bool>& unordered_map, const ResultGraphTableNode *node) {
	return Utilities::isKeyInMap_TypeType(unordered_map, node->getNodeIdentifier());
}

bool ResultGraphTable::checkEdgesHaveAtLeastOneSimilarNode(const edge& e1, const edge& e2) {
	const ResultGraphTableNode* left1 = e1.leftNode;
	const ResultGraphTableNode* right1 = e1.rightNode;
	const ResultGraphTableNode* left2 = e2.leftNode;
	const ResultGraphTableNode* right2 = e2.rightNode;

	const std::string& leftId1 = left1->getNodeIdentifier();
	const std::string& rightId1 = right1->getNodeIdentifier();
	const std::string& leftId2 = left2->getNodeIdentifier();
	const std::string& rightId2 = right2->getNodeIdentifier();

	if (leftId1 == leftId2 || leftId1 == rightId2
		|| rightId1 == leftId2 || rightId1 == rightId2) {
			return true;
	} else {
		return false;
	}
}

// Returns the vector of unique edges gotten from edgesToDestroy - edgesToSave
ResultGraphTable::EdgeMap& ResultGraphTable::getEdgesFromEdgesToDestroyMinusEdgesToSave(const EdgeMap& edgesToDestroy, const EdgeMap& edgesToSave) {	
	// edges to be returned
	EdgeMap *edgesToReturn = new EdgeMap();

	// Add each edge to destroy that is NOT in edge to save into the edgesToReturn
	for (auto it = edgesToDestroy.begin(); it != edgesToDestroy.end(); it++) {
		const edge& e = it->second;
		const std::string& edgeId = getEdgeIdentifier(e);
		if ( !Utilities::isKeyInMap_TypeType(edgesToSave, edgeId)) {
			// Not in edgesToSave, so add it to return
			edgesToReturn->insert( std::pair<string, edge>(edgeId, e) );
		}
	}

	return *edgesToReturn;
}

void ResultGraphTable::destroyEdges(const EdgeMap& edgesToDestroy) {
	// destroy every edge in S, and check the nodes on each side of the edge 
	// if they are connected directly (by looking up the count) to the node of synonymName of the node on the opposite side
	//		of that edge
	// if they are not connected directly, then destroy the node and all its edges, recursively checking the nodes across 
	//		the edges
	if (edgesToDestroy.size() == 0) {
		return;
	}
	//cout << "Size of edgesToDestroy = " << edgesToDestroy.size() << "\n";
	std::vector<edge> edgesToDestroyTemp;
	for (auto it = edgesToDestroy.begin(); it != edgesToDestroy.end(); it++) {
		const edge& edgeToDestroy = it->second;
		edgesToDestroyTemp.push_back(edgeToDestroy);
	}
	for (auto it = edgesToDestroyTemp.begin(); it != edgesToDestroyTemp.end(); it++) {
		destroyEdge(*it);
	}

	std::vector<ResultGraphTableNode> nodesToDestroy;
	for (auto it = edgesToDestroyTemp.begin(); it != edgesToDestroyTemp.end(); it++) {
		const edge& edgeDestroyed = *it;
		const ResultGraphTableNode *left = edgeDestroyed.leftNode;
		const ResultGraphTableNode *right = edgeDestroyed.rightNode;
		const std::string& leftId = left->getNodeIdentifier();
		const std::string& rightId = right->getNodeIdentifier();
		const std::string& leftName = left->getSynonymName();
		const std::string& rightName = right->getSynonymName();
		if (Utilities::isKeyInMap_TypeType(mAdjacentNodeCountMap, leftId)
			&& getCountOfAdjacentNodeOfSynonymName(*left, rightName) <= 0) {
				EdgeMap* leftEdges = getEdgesOfNode(*left, ANY_SYNONYM);
				destroyEdges(*leftEdges);
				nodesToDestroy.push_back(*left);
		}
		if (Utilities::isKeyInMap_TypeType(mAdjacentNodeCountMap, rightId) 
			&& getCountOfAdjacentNodeOfSynonymName(*right, leftName) <= 0) {
				EdgeMap* rightEdges = getEdgesOfNode(*right, ANY_SYNONYM);
				destroyEdges(*rightEdges);
				nodesToDestroy.push_back(*right);
		}
	}
	for (unsigned int i = 0; i < nodesToDestroy.size(); i++) {
		const ResultGraphTableNode& nodeToDestroy = nodesToDestroy.at(i);
		deleteNode(nodeToDestroy);
	}
}

void ResultGraphTable::destroyEdge(const edge& edgeToDestroy) {
	// Destroy the edge by removing it from the vectors which have it in the mEdges unordered_map
	const std::string& edgeToDestroyId = getEdgeIdentifier(edgeToDestroy);
	//cout << "Destroying edge\n";
	const ResultGraphTableNode *left = edgeToDestroy.leftNode;
	const ResultGraphTableNode *right = edgeToDestroy.rightNode;
	const std::string& leftId = left->getNodeIdentifier();
	const std::string& rightId = right->getNodeIdentifier();
	const std::string& leftSynonym = left->getSynonymName();
	const std::string& rightSynonym = right->getSynonymName();
	EdgeMap* leftEdges = mEdges.at(leftId)->at(rightSynonym);
	EdgeMap* rightEdges = mEdges.at(rightId)->at(leftSynonym);
	EdgeMap* anyLeftEdges = mEdges.at(leftId)->at(ANY_SYNONYM);
	EdgeMap* anyRightEdges = mEdges.at(rightId)->at(ANY_SYNONYM);

	/*cout << "edge left = " << leftId << "\n";
	cout << "edge right = " << rightId << "\n";*/
	// remove the edgeToDestroy from each of this vectors
	if (Utilities::isKeyInMap_TypeType(*leftEdges, edgeToDestroyId)) {
		leftEdges->erase( edgeToDestroyId );
	}
	if (Utilities::isKeyInMap_TypeType(*rightEdges, edgeToDestroyId)) {
		rightEdges->erase( edgeToDestroyId );
	}
	if (Utilities::isKeyInMap_TypeType(*anyLeftEdges, edgeToDestroyId)) {
		anyLeftEdges->erase( edgeToDestroyId );
	}
	if (Utilities::isKeyInMap_TypeType(*anyRightEdges, edgeToDestroyId)) {
		anyRightEdges->erase( edgeToDestroyId );
	}

	// Update the count of their adjacent nodes
	const std::string& leftName = left->getSynonymName();
	const std::string& rightName = right->getSynonymName();
	NodeCountMap* nodeCountMapLeft = mAdjacentNodeCountMap.at(leftId);
	NodeCountMap* nodeCountMapRight = mAdjacentNodeCountMap.at(rightId);
	EdgeCountMap* edgeCountMapLeft = mAdjacentEdgeCountMap.at(leftName);
	EdgeCountMap* edgeCountMapRight = mAdjacentEdgeCountMap.at(rightName);

	// Decrease the count by 1
	nodeCountMapLeft->at(rightName)--;
	nodeCountMapRight->at(leftName)--;
	edgeCountMapLeft->at(rightName)--;
	edgeCountMapRight->at(leftName)--;
}

void ResultGraphTable::deleteNode(const ResultGraphTableNode& nodeToDestroy) {
	const std::string& nodeToDestroyId = nodeToDestroy.getNodeIdentifier();
	//cout << "Deleting node = " << nodeId << "\n";
	// erase from mEdges
	if (Utilities::isKeyInMap_TypeType(mEdges, nodeToDestroyId)) {
		delete mEdges.at(nodeToDestroyId);
		mEdges.erase(nodeToDestroyId);
	} 
	// erase from mAdjacentNodeCountMap
	if (Utilities::isKeyInMap_TypeType(mAdjacentNodeCountMap, nodeToDestroyId)) {
		delete mAdjacentNodeCountMap.at(nodeToDestroyId);
		mAdjacentNodeCountMap.erase(nodeToDestroyId);
	}
	// erase from node column under the synonym name
	const std::string& synonymName = nodeToDestroy.getSynonymName();
	if (Utilities::isKeyInMap_TypeType(mColumns, synonymName)) {
		NodeMap* nodeColumn = mColumns.at(synonymName);
		if ( nodeColumn->find(nodeToDestroyId) != nodeColumn->end() ) {
			nodeColumn->erase( nodeToDestroyId );
		}
	}
}

bool ResultGraphTable::checkEdgesEqual(const edge& e1, const edge& e2) {
	const ResultGraphTableNode *left1 = e1.leftNode;
	const ResultGraphTableNode *right1 = e1.rightNode;
	const ResultGraphTableNode *left2 = e2.leftNode;
	const ResultGraphTableNode *right2 = e2.rightNode;

	const std::string& leftId1 = left1->getNodeIdentifier();
	const std::string& rightId1 = right1->getNodeIdentifier();
	const std::string& leftId2 = left2->getNodeIdentifier();
	const ::string& rightId2 = right2->getNodeIdentifier();

	if (leftId1 == leftId2 && rightId1 == rightId2) {
		return true;
	} else {
		return false;
	}
}

bool ResultGraphTable::checkEdgeForNodeOfSynonymName(const edge& e, const std::string& synonymName) {
	const ResultGraphTableNode *left = e.leftNode;
	const ResultGraphTableNode *right = e.rightNode;
	const std::string& leftSynonymName = left->getSynonymName();
	const std::string& rightSynonymName = right->getSynonymName();
	if (leftSynonymName == synonymName
		|| rightSynonymName == synonymName) {
			return true;
	} else {
		return false;
	}
}

// Pops ALL edges from edgesStack off into the edgesVector.
// Returns the popped edges.
std::vector<ResultGraphTable::edge>& ResultGraphTable::popAllEdgesIntoUnorderedMap(std::stack<const edge*> *edgesStack, EdgeMap *edgesMap) {
	std::vector<edge> *poppedEdges = new std::vector<edge>();
	while ( !edgesStack->empty()) {
		const edge *poppedEdge = edgesStack->top();
		edgesStack->pop();
		poppedEdges->push_back(*poppedEdge);
		edgesMap->insert( std::pair<string, edge>(getEdgeIdentifier(*poppedEdge), *poppedEdge) );
	}
	return *poppedEdges;
}

// Pops edges from edgesStack off into the edgesVector, 
// until we find a popped edge shares a similar node to the nextEdge.
// Returns the popped edges.
std::vector<ResultGraphTable::edge>& ResultGraphTable::popEdgesIntoUnorderedMapUntilSimilarNodeReached(std::stack<const edge*> *edgesStack, EdgeMap *edgesMap, 
	const edge& nextEdge) {
		std::vector<edge> *poppedEdges = new std::vector<edge>();
		while ( !edgesStack->empty()) {
			const edge *poppedEdge = edgesStack->top();
			edgesStack->pop();
			poppedEdges->push_back(*poppedEdge);
			edgesMap->insert( std::pair<string, edge>(getEdgeIdentifier(*poppedEdge), *poppedEdge) );
			if (checkEdgesHaveAtLeastOneSimilarNode(*poppedEdge, nextEdge)) {
				// stop popping when we have found a common node
				break;
			}
		}
		return *poppedEdges;
}

// Pops nodes off the nodeStack until there is a node on either side of the nextEdge that is similar to the nextEdge to traverse
const ResultGraphTableNode* ResultGraphTable::popNodesUntilSimillarNodeReached(std::stack<const ResultGraphTableNode*> *nodeStack, const edge& nextEdge) {
	const ResultGraphTableNode *nextNodeToPop = NULL;
	const std::string& leftId = nextEdge.leftNode->getNodeIdentifier();
	const std::string& rightId = nextEdge.rightNode->getNodeIdentifier();
	while ( !nodeStack->empty()) {
		nextNodeToPop = nodeStack->top();

		const std::string& poppedId = nextNodeToPop->getNodeIdentifier();
		if (leftId == poppedId || rightId == poppedId) {
			// stop popping when we have found a common node
			break;
		}

		nodeStack->pop();
	}

	ResultGraphTableNode *nodeToReturn = new ResultGraphTableNode();
	*nodeToReturn = *nextNodeToPop;
	return nodeToReturn;
}

// Pops nodes off the nodeStack until there is a node on either side of the nextEdge that is similar to the nextEdge to traverse
const ResultGraphTableNode* ResultGraphTable::popNodesUntilSimillarNodeReached(std::vector<const ResultGraphTableNode*> *nodeStack, const edge& nextEdge) {
	const ResultGraphTableNode *nextNodeToPop = NULL;
	const std::string& leftId = nextEdge.leftNode->getNodeIdentifier();
	const std::string& rightId = nextEdge.rightNode->getNodeIdentifier();
	while ( !nodeStack->empty()) {
		nextNodeToPop = nodeStack->back();

		const std::string& poppedId = nextNodeToPop->getNodeIdentifier();
		if (leftId == poppedId || rightId == poppedId) {
			// stop popping when we have found a common node
			break;
		}

		nodeStack->pop_back();
	}

	ResultGraphTableNode *nodeToReturn = new ResultGraphTableNode();
	*nodeToReturn = *nextNodeToPop;
	return nodeToReturn;
}

int ResultGraphTable::getCountOfAdjacentNodeOfSynonymName(const ResultGraphTableNode& node, const std::string& synonymName) {
	const std::string& nodeId = node.getNodeIdentifier();
	if ( !Utilities::isKeyInMap_TypeType(mAdjacentNodeCountMap, nodeId)) {
		return -1;
	}

	NodeCountMap* adjacentNodeCountMap = mAdjacentNodeCountMap.at(nodeId);
	if ( !Utilities::isKeyInMap_TypeType(*adjacentNodeCountMap, synonymName)) {
		return -1;
	}

	return adjacentNodeCountMap->at(synonymName);
}

int ResultGraphTable::getCountOfAdjacentEdgesBetween(const std::string &synonym1, const std::string &synonym2) { 
	if ( !Utilities::isKeyInMap_TypeType(mAdjacentEdgeCountMap, synonym1)) {
		// Synonym 1 has not yet been evaluated for
		// return -1 to indicate it
		return -1; 
	}
	if ( !Utilities::isKeyInMap_TypeType(mAdjacentEdgeCountMap, synonym2)) {
		// Synonym 2 has not yet been evaluated for
		// return -2 to indicate it
		return -2; 
	}

	// Here, we are ensured that synonym1 and synonym2 have edge count maps.
	EdgeCountMap *edgeCountMap1 = mAdjacentEdgeCountMap[synonym1];
	if ( !Utilities::isKeyInMap_TypeType(*edgeCountMap1, synonym2)) {
		// Not directly connected to synonym2, return 0.
		return 0;
	}
	// Here, we are ensured that synonym1 and synonym2 have directly connecting edges.
	return edgeCountMap1->at(synonym2);
}

std::vector<int>& ResultGraphTable::getAllIndexes(DesignEntityType synEntityType, PKB *pkb) {
	std::vector<int> *resultIndexes = new std::vector<int>();

	switch (synEntityType) {
	case CONSTANT:
		*resultIndexes = pkb->getConstants();
		break;
	case VARIABLE:
		*resultIndexes = pkb->getVarIndices();
		break;
	case PROCEDURE:
		*resultIndexes = pkb->getProcIndices();
		break;
	default:
		Type::Entity::Line lineEntity;
		lineEntity = SpaEnumTranslator::translateDesignEntityTypeToTypeEntityLine(synEntityType);
		*resultIndexes = pkb->getLinesByEntity(lineEntity);
		break;
	}
	return *resultIndexes;
}

// Returns true if there is at least one node of the specified synonymName
bool ResultGraphTable::isThereAtLeastOneNodeOfSynonymName(const std::string& synonymName) {
	if ( !Utilities::isKeyInMap_TypeType(mHeaders, synonymName) ) {
		return false;
	} else if (mColumns.at(synonymName)->size() > 0) {
		return true;
	} else {
		return false;
	}
}

// Checks, using the pkb, the given indexes vector for indexes which are of the specified synonymEntityType
// and returns only those validated indexes in a vector
std::vector<int>& ResultGraphTable::validateIndexes(const std::vector<int>& indexes, DesignEntityType synonymEntityType, PKB *pkb) {
	std::vector<int> *validatedIndexes = new std::vector<int>();
	std::vector<int>& possibleIndexes = getAllIndexes(synonymEntityType, pkb);

	std::unordered_map<int, bool> possibleIndexMap; // for faster querying
	for (unsigned int i = 0; i < possibleIndexes.size(); i++) {
		possibleIndexMap.insert(std::pair<int, bool>(possibleIndexes.at(i), true));
	}

	for (unsigned int i = 0; i < indexes.size(); i++) {
		int index = indexes.at(i);
		if (Utilities::isKeyInMap_TypeType(possibleIndexMap, index)) {
			validatedIndexes->push_back(index);
		}
	}

	return *validatedIndexes;
}

std::vector<int>& ResultGraphTable::convertLeftSynonymIndexToRightSynonymIndex_VariableOrProcedureOrCall(int synonym1Value, DesignEntityType synonym1Type, DesignEntityType synonym2Type, PKB *pkb) {
		
	std::vector<int> *convertedSynonym2Indexes = new std::vector<int>();
	std::string synonym1NameValue;

	// Possibilities:
	// v.varName = v.varName/p.procName/c2.procName
	// p.procName = v.varName/p.procName/c2.procName
	// c.procName = v.varName/p.procName/c2.procName
	switch (synonym1Type) {
	case VARIABLE:
		synonym1NameValue = pkb->getVarName(synonym1Value);
		break;
	case PROCEDURE:
		synonym1NameValue = pkb->getProcName(synonym1Value);
		break;
	case CALL:
		synonym1NameValue = pkb->getProcName(pkb->getCalledByLine(synonym1Value));
		break;
	default:
		// Shouldn't be here because only variables and procedures have names
		cout << "Error in convertLeftSynonymIndexToRightSynonymIndex_VariableOrProcedureOrCall(): In a conditional branch we shouldn't be in!\n";
		return *convertedSynonym2Indexes;
	}

	switch (synonym2Type) {
	case VARIABLE:
		convertedSynonym2Indexes->push_back(pkb->getVarIndex(synonym1NameValue));
		break;
	case PROCEDURE:
		convertedSynonym2Indexes->push_back(pkb->getProcIndex(synonym1NameValue));
		break;
	case CALL:
		*convertedSynonym2Indexes = pkb->getCallerLineOf(pkb->getProcIndex(synonym1NameValue));
		break;
	default:
		// Shouldn't be here because only variables and procedures have names
		cout << "Error in convertLeftSynonymIndexToRightSynonymIndex_VariableOrProcedureOrCall(): In a conditional branch we shouldn't be in!\n";
		return *convertedSynonym2Indexes;
	}
		
	return *convertedSynonym2Indexes;
}

// Removes all the elements in indexes that are not equal to theIndex.
void ResultGraphTable::leaveOnlyEqualIndexes(std::vector<int> *indexes, int theIndex) {
	std::vector<int> equalIndexes;
	for (auto it = indexes->begin(); it != indexes->end(); it++) {
		if (*it == theIndex) {
			equalIndexes.push_back(*it);
		}
	}
	*indexes = equalIndexes;
}

// Returns true if the specified relType has the same time complexity to find
// out whether relType(1,x) is true/false and to get all the indices x of relType(1,x) that are true.
bool ResultGraphTable::isTimeConsumingRelationship(RelationshipType relType) {
	bool isTimeConsuming = false;
	switch (relType) {
	case AFFECTS_STAR:
		// Fallthrough
	case AFFECTSBIP_STAR:
		// Fallthrough
		isTimeConsuming = true;
		break;
	default:
		isTimeConsuming = false;
		break;
	}
	return isTimeConsuming;
}

void ResultGraphTable::updateWithNewRelationshipForEqualSynonyms(const std::string& synonym1, const std::string& synonym2, RelationshipType relType, 
	PKB *pkb, SynonymTable *synonymTable) {
		// Only NEXTBIP_STAR, NEXT_STAR, AFFECTS, AFFECTS_STAR, EQuALS_NAME, or EQUALS_INDEX
		// will possibly have an answer since the synonyms are equal!
		switch (relType) {
		case EQUALS_NAME:
			// Fallthrough:
		case EQUALS_INDEX:
			// Fallthrough:
		case NEXT_STAR:
			// Fallthrough
		case AFFECTS:
			// Fallthrough
		case AFFECTS_STAR:
			// Fallthrough
		case NEXTBIP_STAR:
			// Fallthrough
		case AFFECTSBIP:
			// Fallthrough
		case AFFECTSBIP_STAR:
			// Initialize a column for it if it is not yet initialized,
			// adding all possible indexes to the column
			if ( !isSynonymInTable(synonym1)) {
				cout << "Initializing column for " << synonym1 << endl;
				const ResultGraphTableNode& synonymHeaderNode = initializeColumn(synonym1);
				linkNodes(synonymHeaderNode, synonymHeaderNode);

				DesignEntityType synEntityType = synonymTable->getDesignEntityType(synonym1);
				std::vector<int>& synIndexes = getAllIndexes(synEntityType, pkb);
				unsigned int synIndexesSize = synIndexes.size();
				for (unsigned int i = 0; i < synIndexesSize; i++) {
					int synonymResult = synIndexes.at(i);
					const ResultGraphTableNode *synonymResultNode =
						addResultNodeUniquelyToColumn(synonym1, synonymResult);
					linkNodes(*synonymResultNode, *synonymResultNode);
				}
			}

			cout << "ResultGraphTable: updateWithNewRelationshipForBothSynonymsInTable\n";
			// Now, we the column must exist, and we can treat it as if both synonyms 1 and 2 are in the table.
			updateWithNewRelationshipForBothSynonymsInTable(synonym1, synonym2, relType,
															pkb, synonymTable);
		default:
			break;
		}
}

void ResultGraphTable::updateWithNewRelationshipForBothSynonymsNotInTable(const std::string& synonym1, const std::string& synonym2, RelationshipType relType, 
	PKB *pkb, SynonymTable *synonymTable) {

		const ResultGraphTableNode& synonym1HeaderNode = initializeColumn(synonym1);
		const ResultGraphTableNode& synonym2HeaderNode = initializeColumn(synonym2);
		linkNodes(synonym1HeaderNode, synonym2HeaderNode);
			
		std::vector<std::pair<int, std::vector<int>>>& trueRelationshipPairs = getAllTrueRelationshipPairs(pkb, synonymTable, relType, synonym1, synonym2);
		
		std::clock_t start;
		double duration;

		start = std::clock(); // time how long all the node-linking takes

		// Add all trueRelationshipPairs to the table, establishing links
		for (unsigned int i = 0; i < trueRelationshipPairs.size(); i++) {
			std::pair<int, std::vector<int>>& pair = trueRelationshipPairs.at(i);
			int synonym1Result = pair.first;
			const ResultGraphTableNode *synonym1ResultNode = 
				addResultNodeUniquelyToColumn(synonym1, synonym1Result);

			std::vector<int>& synonym2Results = pair.second;
			for (unsigned int j = 0; j < synonym2Results.size(); j++) {
				int synonym2Result = synonym2Results.at(j);
				const ResultGraphTableNode *synonym2ResultNode = 
					addResultNodeUniquelyToColumn(synonym2, synonym2Result);
				linkNodes(*synonym1ResultNode, *synonym2ResultNode);
			}
		}
		
		duration = ( std::clock() - start ) / (double) CLOCKS_PER_SEC;
		//cout << "updateWithNewRelationshipForBothSynonymsNotInTable() node-linking for relType " << relType << " took " << duration << " seconds\n";	
			
		ensureDirectLinkRemainOnly(synonym1, synonym2);
}

void ResultGraphTable::updateWithNewRelationshipForLeftSynonymInTable(const std::string& synonym1, const std::string& synonym2, RelationshipType relType, 
	PKB *pkb, SynonymTable *synonymTable) {
		
		const ResultGraphTableNode& synonym2HeaderNode = initializeColumn(synonym2);
		const ResultGraphTableNode& synonym1HeaderNode = *(mHeaders.at(synonym1));
		linkNodes(synonym1HeaderNode, synonym2HeaderNode);

		// Establish links between existing synonym1 result nodes and to new (which we will add here) synonym2 result nodes
		NodeMap* synonym1Column = mColumns.at(synonym1);
		for (auto it = synonym1Column->begin(); it != synonym1Column->end(); it++) {
			const ResultGraphTableNode *synonym1ResultNode = it->second;
			int synonym1Result = synonym1ResultNode->getNodeValue();

			std::vector<int>& syn2IndexesForGivenSyn1Index = getTrueRelationshipSynonym2IndexesForGivenSynonym1Index(pkb, synonymTable,
																						relType, synonym1, synonym2, synonym1Result);
			
			for (unsigned int j = 0; j < syn2IndexesForGivenSyn1Index.size(); j++) {
				int synonym2Result = syn2IndexesForGivenSyn1Index.at(j);
				const ResultGraphTableNode *synonym2ResultNode = 
					addResultNodeUniquelyToColumn(synonym2, synonym2Result);
				linkNodes(*synonym1ResultNode, *synonym2ResultNode);
			}
		}

		ensureDirectLinkRemainOnly(synonym1, synonym2);
}

void ResultGraphTable::updateWithNewRelationshipForRightSynonymInTable(const std::string& synonym1, const std::string& synonym2, RelationshipType relType, 
	PKB *pkb, SynonymTable *synonymTable) {
		
		const ResultGraphTableNode& synonym1HeaderNode = initializeColumn(synonym1);
		const ResultGraphTableNode& synonym2HeaderNode = *(mHeaders.at(synonym2));
		linkNodes(synonym1HeaderNode, synonym2HeaderNode);

		// Establish links between existing synonym2 result nodes and to new (which we will add here) synonym1 result nodes
		NodeMap* synonym2Column = mColumns.at(synonym2);
		for (auto it = synonym2Column->begin(); it != synonym2Column->end(); it++) {
			const ResultGraphTableNode *synonym2ResultNode = it->second;
			int synonym2Result = synonym2ResultNode->getNodeValue();

			std::vector<int>& syn1IndexesForGivenSyn2Index = getTrueRelationshipSynonym1IndexesForGivenSynonym2Index(pkb, synonymTable,
																						relType, synonym1, synonym2, synonym2Result);

			for (unsigned int j = 0; j < syn1IndexesForGivenSyn2Index.size(); j++) {
				int synonym1Result = syn1IndexesForGivenSyn2Index.at(j);
				const ResultGraphTableNode *synonym1ResultNode = 
					addResultNodeUniquelyToColumn(synonym1, synonym1Result);
				linkNodes(*synonym1ResultNode, *synonym2ResultNode);
			}
		}
		
		ensureDirectLinkRemainOnly(synonym2, synonym1);
}

void ResultGraphTable::updateWithNewRelationshipForBothSynonymsInTable(const std::string& synonym1, const std::string& synonym2, RelationshipType relType, 
	PKB *pkb, SynonymTable *synonymTable) {
		
		if ( !isSynonymRelatedToSynonym(synonym1, synonym2)) {
			// synonym1 and synonym2 are not related, even indirectly
			const ResultGraphTableNode& synonym1HeaderNode = *(mHeaders.at(synonym1));
			const ResultGraphTableNode& synonym2HeaderNode = *(mHeaders.at(synonym2));
			linkNodes(synonym1HeaderNode, synonym2HeaderNode);

			DesignEntityType synonym1Type = synonymTable->getDesignEntityType(synonym1);
			DesignEntityType synonym2Type = synonymTable->getDesignEntityType(synonym2);
			NodeMap* synonym1Column = mColumns.at(synonym1);
			NodeMap* synonym2Column = mColumns.at(synonym2);
			// Establish links between existing synonym1 and synonym2 result nodes
			for (auto it1 = synonym1Column->begin(); it1 != synonym1Column->end(); it1++) {
				const ResultGraphTableNode *synonym1Node = it1->second;
				int synonym1Result = synonym1Node->getNodeValue();
				for (auto it2 = synonym2Column->begin(); it2 != synonym2Column->end(); it2++) {
					const ResultGraphTableNode *synonym2Node = it2->second;
					int synonym2Result = synonym2Node->getNodeValue();

					bool isTrueRelationship = checkIfIsTrueRelationship(pkb, relType, synonym1Result, synonym2Result, 
																		synonym1Type, synonym2Type);
					if (isTrueRelationship) {
						linkNodes(*synonym1Node, *synonym2Node);
					}
				}
			}

			ensureDirectLinkRemainOnly(synonym1, synonym2);
			ensureDirectLinkRemainOnly(synonym2, synonym1);
		} else {
			// synonym1 and synonym2 are related
			// aim to delete edges (no establishing new edges)
			NodeMap* synonym1Column = mColumns.at(synonym1);
			PathMap& pathMap = findPathFromSynonymToSynonym(synonym1, synonym2);
			//cout << "PathMap from " << synonym1 << " to " << synonym2 << "\n";
			//for (auto it = pathMap.begin(); it != pathMap.end(); it++) {
				//cout << it->first << " -> " << it->second << "\n";
			//}
			// Special-depth-first search from each startingNode from the starting column,
			// attempting to reach a node of synonym2 to test if the relationship 
			// between the startingNode and the node of synonym2 holds.
			// While traversing, we insert the set of edges traversed in a path in a set called edgesToDestroyTemp.
			// edgesToDestroyTemp will ONLY be used when a node of synonym2 is reached;
			// Upon reaching a node of synonym2, if the relationship holds between the starting node and the synonym2 node,
			// all the edges in edgesToDestroyTemp will be transferred to another set of edges edgesToSave.
			// If the relationship does not hold, the edges in edgesToDestroyTemp will be transferred to another set of edges edgesToDestroy.
			// At the end of everything, we destroy those edges in the edgesToDestroy set but not in the edgesToSave set,
			// and check all the nodes connected to each of these destroyed edges.
			// If a node checked in this manner is found to have no connection to, simultaneously, BOTH synonym1 and synonym2,
			// then we delete this node and its edges, and recursively perform the same check on all the nodes it was connected to.
			std::unordered_map<std::string, edge> edgesToDestroy; // to be used at the end
			std::unordered_map<std::string, edge> edgesToSave; // to be used at the end
				
			std::clock_t start;
			double duration;

			start = std::clock(); // time how long all the performTraversalForRelationshipEvaluation() takes

			for (auto it = synonym1Column->begin(); it != synonym1Column->end(); it++) {
				const ResultGraphTableNode *startingNode = it->second;

				ResultGraphTableNode currentNode = *startingNode;

				performTraversalForRelationshipEvaluation(pkb, synonymTable,
															relType,
															synonym1,
															synonym2,
															startingNode,
															&currentNode,
															&edgesToDestroy,
															&edgesToSave,
															pathMap);
			}

			duration = ( std::clock() - start ) / (double) CLOCKS_PER_SEC;
			//cout << "performTraversalForRelationshipEvaluation() loop for relType " << relType << " took " << duration << " seconds\n";	
			// Get the set S which are edges in the set edgesToDestroy but not in the set edgesToSave,
			// destroy every edge in S, and check the nodes on each side of the edge 
			// if they are connected directly (by looking up the count) to the node of synonymName of the node on the opposite side
			//		of that edge
			// if they are not connected directly, then destroy the node and all its edges, recursively checking the nodes across 
			//		the edges
			/*
			cout << "Edges to destroy contains:\n";
			for (auto it = edgesToDestroy.begin(); it != edgesToDestroy.end(); it++) {
				cout << it->first;
			}
			cout << endl;
			cout << "Edges to save contains:\n";
			for (unsigned int i = 0; i < edgesToSave.size(); i++) {
				edge e = edgesToSave.at(i);
				if (checkEdgeForNodeOfSynonymName(e, "a")) {
					cout << getEdgeIdentifier(e) << '\n';
				}
			}*/
			EdgeMap& finalEdgesToDestroy = getEdgesFromEdgesToDestroyMinusEdgesToSave(edgesToDestroy, edgesToSave);
			/*cout << "Final edges to destroy contains:\n";
			for (auto it = finalEdgesToDestroy.begin(); it != finalEdgesToDestroy.end(); it++) {
				edge e = it->second;
				if (checkEdgeForNodeOfSynonymName(e, "a")) {
					cout << getEdgeIdentifier(e) << '\n';
				}
			}*/
			// destroy edges
			destroyEdges(finalEdgesToDestroy);
		}
}

Table<std::string, int>& ResultGraphTable::getTuples(std::unordered_map<std::string, bool> synonymsRequiredMap, 
	SynonymTable *synonymTable, PKB *pkb) {

	//cout << "DEBUGGING: ResultGraphTable::getTuples()\n";
	std::clock_t start;
	double duration;

	start = std::clock(); // time how long getTuples() takes
	/**-----------------------------------------------------------------------------------
	 *	ALGORITHM for tuple-finding
	 *
	 *	Maintain:
	 *	1. The synonymsRequiredMap, S, on-the-go for use during graph-traversal.
	 *	2. A map of SynonymResultsTablePtrs, T, for merging at the end.
	 *
	 *	Pseudocode:
	 *	while S is not empty,
	 *		s1 <- first synonym in S
	 *		for each synonym X != first synonym in S
	 *			Find out if s1 is related to X.
	 *			If related,
	 *				then perform a traversal with the purpose of
	 *				finding tuples and creating a tupleTable to be stored into T.
	 *				(During this step, S will reduce in size by the number of 
	 *				synonyms for which tuples have been found)
	 *			else
	 *				continue until all X's have been checked.
	 *		end for
	 *	end while
	 *	while T is not of size 1,
	 *		for every pair of (t1, t2) in T,
	 *			merge t1 and t2 into a new t1 such that new t1 has the size of t1 * t2
	 *			re-insert new t1 into T
	 *		end for
	 *	end while
	 *	return the only t in T
	 *-----------------------------------------------------------------------------------*/
	std::unordered_map<std::string, SynonymResultsTable*> tablesMap;
	
	// While S is not empty
	while ( !synonymsRequiredMap.empty()) {
		// Maintain the synonyms for which tuples have been found in every iteration
		// so that we do not delete during the iteration and make the iterator invalid.
		std::unordered_map<std::string, bool> synonymsDoneMap;
		// s1 <- first synonym in S
		const std::string& synonym1 = synonymsRequiredMap.begin()->first;

		/**------------------------------
		 *	Create a table for synonym1
		 *-------------------------------*/
		SynonymResultsTable *table1 = new SynonymResultsTable();
		table1->insertColumn(synonym1);
		// Get the row indexes of s1
		DesignEntityType synEntityType = synonymTable->getDesignEntityType(synonym1);
		std::vector<int> syn1Indexes = getResultIndexesForSynonym(synonym1, synEntityType, pkb);
		// Put the row indexes of s1 into the table
		for (unsigned int i = 0; i < syn1Indexes.size(); i++) {
			table1->appendEntry(synonym1, syn1Indexes.at(i));
		}
		// Put the table into the map
		tablesMap[synonym1] = table1;
		//cout << "DEBUGGING: Put table for " << synonym1 << " into map\n";


		bool mustRepeat = false; // Must repeat if synonymX is not synonym2
		do {
			
			// Put synonym1 into the done map to ensure that we don't pick it later during
			// the for loop.
			synonymsDoneMap[synonym1] = true;

			mustRepeat = false;
			// for each synonym X != first synonym in S
			// Note: it++ initialize is to ensure that 
			//		we are not at the first synonym in S.
			for (auto it = synonymsRequiredMap.begin(); it != synonymsRequiredMap.end(); it++) {
				const std::string& synonym2 = it->first;
				// Find out if s1 is related to X. Also, ensure that synonym2 isn't done already.
				if ( !Utilities::isKeyInMap_TypeType(synonymsDoneMap, synonym2) && 
					isSynonymRelatedToSynonym(synonym1, synonym2)) {
						// then perform a traversal with the purpose of
						// finding tuples and creating a tupleTable to be stored into T.
						// (During this step, S will reduce in size by the number of 
	 					// synonyms for which tuples have been found)
						//cout << "DEBUGGING: synonym2 " << synonym2 << 
						//	" not in doneMap, and is related to synonym2 " << synonym2 << endl; 
						// We want to perform a traversal first on a synonym2 nearest to synonym1
						// So we look at this path and traverse from synonym1 to synonym2,
						// looking for the first synonym along this path that is 
						// in S.
						PathMap& pathMap = findPathFromSynonymToSynonym(synonym1, synonym2);
						std::string nextSynonym = synonym1;
						do {
							//cout << "DEBUGGING: nextSynonym: " << nextSynonym << endl;
							nextSynonym = pathMap.at(nextSynonym);
						} while (nextSynonym != synonym2 && 
							!Utilities::isKeyInMap_TypeType(synonymsRequiredMap, nextSynonym));
						// 2 possibilities: nextSynonym == synonym2 OR nextSynonym is
						//		the synonym nearer to synonym1 that we are looking for
						const std::string& synonymX = nextSynonym;
						//cout << "DEBUGGING: synonymX: " << synonymX << endl;
						if (synonymX != synonym2) {
							// Must repeat with synonym1 as long as synonym2 is not used
							// TODO SQueriestuple 4
							//cout << "DEBUGGING: synonymX " << synonymX << " not equals to synonym2 " << synonym2 <<
							//	" so set mustRepeat to true \n";
							mustRepeat = true;
							synonymsDoneMap.erase(synonym1);
						}
						//cout << "Debugging: Gonna perform a traversal\n";
						// X has been found. Perform traversal!
						// Ensure that tablesMap is only inserted a table for
						// the first argument (synonym1) all the time,
						// in order to ensure that only one element is inserted for each 
						// time a table is formed. 
						// (This is to simplify the later merging step)
						performTraversalForTupleFinding(synonym1, synonymX, &tablesMap, synonymsRequiredMap);
						// Put synonymX into the synonymsDoneMap
						synonymsDoneMap[synonymX] = true;
				} else {
					// continue until all X's have been checked.
					continue;
				}
			}

			// Remove all the done synonyms from S
			// (these done synonyms were gotten from S in the first place,
			// so we are ensured that they are inside S (and can erase without checking)
			for (auto iter = synonymsDoneMap.begin(); iter != synonymsDoneMap.end(); iter++) {
				const std::string& synonymDone = iter->first;
				//cout << "Erasing synonym " << synonymDone << " from synonymsRequiredMap\n";
				synonymsRequiredMap.erase(synonymDone);
			}
		
		} while (mustRepeat);
	}

	// Here, we are ensured that T is at least of size 1.
	// Otherwise, just print a message and return an empty table.
	if (tablesMap.empty()) {
		cout << "Error in ResultGraphTable getTuples()! tablesMap should NOT be empty!\n";
		SynonymResultsTable *finalTuplesTable = new Table<std::string, int>();
		return *finalTuplesTable;
	}

	// while T is not of size 1,
	while (tablesMap.size() != 1) {
		// for a pair of (t1, t2) in T,
		auto it = tablesMap.begin();
		const std::string& table1Synonym = it->first;
		SynonymResultsTable *table1 = it->second;
		it++;
		const std::string& table2Synonym = it->first;
		SynonymResultsTable *table2 = it->second;

		//cout << "Gonna merge tables\n";
		// Merge t1 and t2 into a new t1
		mergeTwoTupleTables(table1, *table2);
		
		// Re-insert new t1 into T
		tablesMap[table1Synonym] = table1;

		// Erase table2 (got table2Synonym from T itself, 
		// so no need to check before erasing
		tablesMap.erase(table2Synonym);
	}

	duration = ( std::clock() - start ) / (double) CLOCKS_PER_SEC;
	//cout << "ResultGraphTable getTuples() took " << duration << " seconds\n";

	 // Here, we are ensured that T is of size 1. Return that only t in T.
	return *(tablesMap.begin()->second);
}

void ResultGraphTable::performTraversalForTupleFinding(const std::string& synonym1, const std::string& synonym2,
	std::unordered_map<std::string, SynonymResultsTable*> *tablesMap, const std::unordered_map<std::string, bool>& synonymsRequiredMap) {
		/**-----------------------------------------------------------------------------------
		 *	ALGORITHM for graph-traversal for tuple-finding
		 *	Ensure that synonym1 and synonym2 are related and different,
		 *	and that the tablesMap given contains a table for synonym1.
		 *	This function traverses the graph starting from synonym1, for each of its nodes,
		 *	and aims to look for synonym2. Once it reaches synonym2, it will insert a tuple for synonym1
		 *	and synonym2 into the correct table as given in the tableMap keyed by synonym1
		 *	(if it doesn't exist there, then this creates a table and puts it there).
		 *
		 *	First, finds all the tuples <synonym1,synonym2> and stores it in a map M
		 *	in which the key is the synonym1 value, and the item is the list of synonym 2.
		 *	Then, walk through each row of the table keyed by synonym1,
		 *	checking the value of the index of synonym1 at each row to see if it is in M.
		 *	If it is, 
		 *		then look at how many indexes of synonym2 is there for the index,
		 *		and duplicate the row of t1 by that number - 1,
		 *		and fill in all the indexes of synonym2 into its column.
		 *	Otherwise,
		 *		just continue to the next row.
		 *-----------------------------------------------------------------------------------*/
		// Ensure related
		if (!isSynonymRelatedToSynonym(synonym1, synonym2)) {
			cout << "Error in ResultGraphTable performTraversalForTupleFinding(): synonym1 and synonym2 not related!\n";
			return;
		}
		// Ensure different
		if (synonym1 == synonym2) {
			cout << "Error in ResultGraphTable performTraversalForTupleFinding(): synonym1 == synonym2! No tuples for this!\n";
			return;
		}
		// Ensure there is a table for synonym1 in the tablesMap
		if ( !Utilities::isKeyInMap_TypeType(*tablesMap, synonym1)) {
			cout << "Error in ResultGraphTable performTraversalForTupleFinding(): No table for synonym1 in tablesMap!\n";
			return;
		}

		// Here, we are ensured that synonym1 and synonym2 are related and different
		// and that the tablesMap given contains a table for synonym1.
		
		// First, finds all the tuples <synonym1,synonym2> and stores it in a map M
		// in which the key is the synonym1 value, and the item is the list of synonym 2.
		// TRAVERSE!
		PathMap& pathMap = findPathFromSynonymToSynonym(synonym1, synonym2);

		// Find the synonym on this path that is nearest to synonym2 that is in the table
		SynonymResultsTable *table1 = tablesMap->at(synonym1);
		// Ensure that this table1 does not already have a synonym2 column.
		// If it does, there is no need to evaluate for it.
		if (table1->doesHeaderExist(synonym2)) {
			return;
		}
		const std::string& nearestSynonym = findNearestSynonym(synonym1, synonym2, pathMap, *table1);
		//cout << "DEBUGGING: nearestSynonym: " << nearestSynonym << endl;
		// Start traversal from the nodes of the nearest synonym,
		// using table1.
		const Table<std::string, int>::Column& nearestSynonymColumn = table1->getColumn(nearestSynonym);
		const std::vector<std::string>& headers = table1->getHeaders();
		std::vector<int> synonym2IndexesToAppend;
		for (unsigned int row = 0; row < nearestSynonymColumn.size(); row++) {
			// Start the node from the current nearestSynonym
			const ResultGraphTableNode *currentNode = new ResultGraphTableNode(nearestSynonym, nearestSynonymColumn.at(row));
			const ResultGraphTableNode startingNode = *currentNode;
			//cout << "\n\nDEBUGGING: new starting node: " << startingNode.getNodeIdentifier() << '\n';
			
			std::vector<const ResultGraphTableNode*> nodeStack;
			// Add all nodes in the row into the nodeStack.
			for (unsigned int h = 0; h < headers.size(); h++) {
				const std::string& header = headers.at(h);
				if (header != nearestSynonym) {
					const ResultGraphTableNode *otherNode = new ResultGraphTableNode(header, table1->getEntry(header, row));
					nodeStack.push_back(otherNode);
				}
			}

			std::vector<const ResultGraphTableNode*> badEdgeCheckingNodes = getBadEdgeCheckingNodes(*currentNode);


			//cout << "DEBUGGING: Traversing: currentNode = " << currentNode->getNodeIdentifier() << '\n';

			int nearestSynonymValue = currentNode->getNodeValue();

			std::unordered_map<std::string, bool> nodeVisitedMap;
			std::stack<edge> edgesStack;
			std::string prevNodeSynonymName = ""; // so that edges of the node we just came from is not traversed
			const std::string& currentNodeSynonymName = currentNode->getSynonymName();
			const std::string& nextNodeSynonymName = pathMap.at(currentNodeSynonymName);
			EdgeMap* currentEdges = getEdgesOfNode(*currentNode, nextNodeSynonymName);
			for (auto it = currentEdges->begin(); it != currentEdges->end(); it++) {
				const edge& e = it->second;
				//cout << "DEBUGGING: Traversing: PUSH edge OR NOT? for traversal later: " << getEdgeIdentifier(e) << endl;
				if ( //!isBadEdge(startingNode, e)
					isGoodEdge(startingNode, e) || !isBadEdge(startingNode, e)) { // DEBUGGING
						// Only push the edge if its not a bad edge
						//cout << "Debugging: Traversing: Pushed edge: " << getEdgeIdentifier(e) << '\n';
						edgesStack.push(e);
				}
			}
			// Mark currentNode as visited because edges have been added to the stack
			nodeVisitedMap.insert(std::pair<std::string, bool>(currentNode->getNodeIdentifier(), true));

			// maintain a stack of nodes that we are traversing
			nodeStack.push_back(currentNode);

			// DEBUGGING
			/*cout << "DEBUGGING: Traversing: nodeStack: ";
			for (auto it = nodeStack.begin(); it != nodeStack.end(); it++) {
				cout << (*it)->getNodeIdentifier() << " ";
			}
			cout << endl;
			cout << "DEBUGGING: Size of edgesStack: " << edgesStack.size() << endl;*/
			
			std::vector<int> synonym2Indexes;
			// Keep traversing, looking for nodes of synonym2
			//cout << "DEBUGGING: Traversing: Right before while loop\n";
			while ( !edgesStack.empty()) {
				//cout << "DEBUGGING: Traversing: Entered while loop\n";
				// traverse the edge to the node that is not yet visited,
				// check if it is a node of synonym2,
				// if it is not, 
				//		then we add all the edges of the node that connect to the next synonym in the pathmap.
				// if it is,
				//		then we do not add any edges of the node, but instead add synonym2 value to M
				//		then, pop off all the nodes until the next edge to traverse (if there is one).

				// Pop the edge off the stack and into a edgesToDestroyTemp stack of edges
				const edge& currentEdge = edgesStack.top();
				edgesStack.pop();

				// traverse the edge to the node that is not the one we are on currently
				prevNodeSynonymName = currentNode->getSynonymName();
				const ResultGraphTableNode *leftNode = currentEdge.leftNode;
				const ResultGraphTableNode *rightNode = currentEdge.rightNode;
				const std::string& leftId = leftNode->getNodeIdentifier();
				const std::string& currentId = currentNode->getNodeIdentifier();

				if (leftId == currentId) {
					// leftNode is the currentNode, so traverse right
					currentNode = rightNode;
				} else {
					// leftNode is NOT the currentNode, so traverse there (left)
					currentNode = leftNode;
				}
				nodeStack.push_back(currentNode);
				/*cout << "DEBUGGING: Traversing: Traversed to " << currentNode->getNodeIdentifier() << endl;
				cout << "DEBUGGING: Traversing: nodeStack: ";
				for (auto it = nodeStack.begin(); it != nodeStack.end(); it++) {
					cout << (*it)->getNodeIdentifier() << " ";
				}
				cout << endl;*/
			
				// check if the node is a node of synonym2
				if (currentNode->getSynonymName() != synonym2) {
					// currentNode is not a node of synonym
					//		then only add the edges of the node if it has not been visited before.
					//		else continue
					if ( !Utilities::isKeyInMap_TypeType(nodeVisitedMap, currentNode->getNodeIdentifier())) {
						const std::string& currentNodeSynonymName = currentNode->getSynonymName();
						const std::string& nextNodeSynonymName = pathMap.at(currentNodeSynonymName);
						currentEdges = getEdgesOfNode(*currentNode, nextNodeSynonymName);
						bool wasAnyEdgePushed = false;
						for (auto it = currentEdges->begin(); it != currentEdges->end(); it++) {
							const edge& e = it->second;
							//cout << "DEBUGGING: Traversing: PUSH edge OR NOT? for traversal later: " << getEdgeIdentifier(e) << endl;
							if ( //!isBadEdge(nodeStack, e, synonymsRequiredMap)
								isGoodEdge(startingNode, e) || !isBadEdge(nodeStack, e, synonymsRequiredMap)) { // DEBUGGING
									// Only add edges that are not in the badEdgeMap
									//cout << "DEBUGGING: Traversing: Pushed edge: " << getEdgeIdentifier(e) << '\n';
									edgesStack.push(e);
									wasAnyEdgePushed = true;
							}
						}
						// Mark currentNode as visited because edges have been added to the stack
						nodeVisitedMap.insert(std::pair<std::string, bool>(currentNode->getNodeIdentifier(), true));

						// If no edge was pushed, we need to pop nodes off the nodestack
						// Pop off all nodes until the next edge to traverse if there is one
						if ( !edgesStack.empty()) {
							const edge& nextEdgeToTraverse = edgesStack.top();
							currentNode = popNodesUntilSimillarNodeReached(&nodeStack, nextEdgeToTraverse);
							//cout << "DEBUGGING: Traversing: POPPING NODES OFF\n";
						}
					} else {
						// Node visited before! Ignore it.
						continue;
					}
				} else {
					// currentNode is a node of synonym2
					//		then we do not add any edges of the node, but instead add synonym2 value to M if not visited
					//		then, pop off all the nodes until the next edge to traverse (if there is one).
					//		If visited before, ignore it
					if ( !Utilities::isKeyInMap_TypeType(nodeVisitedMap, currentNode->getNodeIdentifier())) {
						int synonym2Value = currentNode->getNodeValue();
						//cout << "Found a tuple <" << nearestSynonymValue << ',' << synonym2Value << ">\n";
						synonym2Indexes.push_back(synonym2Value);
				
						nodeVisitedMap[currentNode->getNodeIdentifier()] = true;						
					}
					// Pop off all nodes until the next edge to traverse if there is one
					if ( !edgesStack.empty()) {
						const edge& nextEdgeToTraverse = edgesStack.top();
						currentNode = popNodesUntilSimillarNodeReached(&nodeStack, nextEdgeToTraverse);
						//cout << "DEBUGGING: Traversing: POPPING NODES OFF\n";
					}
				}
			} // end of traversal from one node of nearestSynonym

			//cout << "DEBUGGING: Ended Traversal\n\n";

			// Time to duplicate rows and add in all the synonyms
			if ( !table1->doesHeaderExist(synonym2)) {
				// Add the column in if it doesn't exist
				table1->insertColumn(synonym2);
			}
			int numRowsNeeded = synonym2Indexes.size();
			if (numRowsNeeded > 1) {
				// Duplicate rows if more than 1 needed
				table1->duplicateRow(row, numRowsNeeded - 1);
			}
			if (numRowsNeeded != 0) {
				// There is at least 1 row needed, so put that in first
				int synonym2Index = synonym2Indexes.at(0);
				table1->appendEntry(synonym2, synonym2Index);
			}
			// Put the rest into a vector to append later
			for (unsigned int i = 1; i < synonym2Indexes.size(); i++) {
				int synonym2Index = synonym2Indexes.at(i);
				synonym2IndexesToAppend.push_back(synonym2Index);
			}
		} // end of ALL traversals from synonym1 nodes
		// Now we append
		for (auto it = synonym2IndexesToAppend.begin(); it != synonym2IndexesToAppend.end(); it++) {
			table1->appendEntry(synonym2, *it);
		}
}

void ResultGraphTable::mergeTwoTupleTables(SynonymResultsTable *table1, const SynonymResultsTable& table2) {
	/**-----------------------------------------------------------------------------------
	 *	ALGORITHM for merging 2 tuple tables, t1 and t2
	 *
	 *	For every row r1 in table1, 
	 *	appends (and duplicates if necessary - when there is more than one row r2)
	 *	every row r2 from table2 onto it. 
	 *	table1 will be the resultant table of the merge at the end.
	 *-----------------------------------------------------------------------------------*/
	if (table2.getNumRows() == 0) {
		// Nothing to append
		return;
	}

	// Insert the columns of table2 into table1
	const std::vector<string>& table2Headers = table2.getHeaders();
	for (unsigned int i = 0; i < table2Headers.size(); i++) {
		const std::string& table2Header = table2Headers.at(i);
		table1->insertColumn(table2Header);
	}

	// Append rows from table2 onto table1, duplicating rows if necessary
	int numRowsToAppend = table2.getNumRows();
	int numRowsTable1Originally = table1->getNumRows();
	for (int row = 0; row < numRowsTable1Originally; row ++) {
		if (numRowsToAppend > 1) {
			// Need to duplicate rows
			table1->duplicateRow(row, numRowsToAppend - 1);
		}
		if (numRowsToAppend != 0) {
			// Have at least one row to append, so append one row first
			for (unsigned int i = 0; i < table2Headers.size(); i++) {
				const std::string& header = table2Headers.at(i);
				int index = table2.getEntry(header, 0);
				table1->appendEntry(header, index);
			}
		}
	}
	// Now append all the table2 rows excluding the first one, 
	// #table1->getNumRows() number of times
	for (int row = 0; row < numRowsTable1Originally; row++) {
		for (int i = 1; i < numRowsToAppend; i++) {
			for (unsigned int j = 0; j < table2Headers.size(); j++) {
				const std::string& header = table2Headers.at(j);
				int index = table2.getEntry(header, i);
				table1->appendEntry(header, index);
			}
		}
	}
}

// Checks if the edge e is a good edge for the node
bool ResultGraphTable::isGoodEdge(const ResultGraphTableNode& node, const edge& e) {
	if ( !Utilities::isKeyInMap_TypeType(mGoodEdgeMapPtrs, node.getNodeIdentifier())) {
		return false;
	} else {
		const BadEdgeMap *goodEdgeMap = mGoodEdgeMapPtrs[node.getNodeIdentifier()];
		const std::string& edgeId = getEdgeIdentifier(e);
		if (Utilities::isKeyInMap_TypeType(*goodEdgeMap, edgeId)) {
			return true;
		} else {
			return false;
		}
	}
}

bool ResultGraphTable::isBadEdge(const ResultGraphTableNode& node, const edge& e) {
	// Get the BadEdgeMap for the nodes
	if ( !Utilities::isKeyInMap_TypeType(mBadEdgeMapPtrs, node.getNodeIdentifier())) {
		return false;
	} else {
		const BadEdgeMap *badEdgeMap = mBadEdgeMapPtrs[node.getNodeIdentifier()];
		const std::string& edgeId = getEdgeIdentifier(e);
		if (Utilities::isKeyInMap_TypeType(*badEdgeMap, edgeId)) {
			return true;
		} else {
			return false;
		}
	}
}

bool ResultGraphTable::isBadEdge(const std::vector<const ResultGraphTableNode*>& nodes, const edge& e, const std::unordered_map<string, bool>& synonymsRequiredMap) {
	const ResultGraphTableNode *leftNode = e.leftNode;
	const ResultGraphTableNode *rightNode = e.rightNode;
	const std::string& leftNodeId = leftNode->getNodeIdentifier();
	const std::string& rightNodeId = rightNode->getNodeIdentifier();
	if (isBadEdge(*leftNode, e) || isBadEdge(*rightNode, e)) {
		return true;
	}
	for (unsigned int i = 0; i < nodes.size(); i++) {
		const ResultGraphTableNode *node = nodes.at(i);
		const std::string& synonym = node->getSynonymName();
		if (Utilities::isKeyInMap_TypeType(synonymsRequiredMap, synonym)
			&& isBadEdge(*node, e)) {
			 return true;
		}
	}
	return false;
}

std::string ResultGraphTable::findNearestSynonym(const std::string& synonym1, const std::string& synonym2, 
	const PathMap& pathMap, const SynonymResultsTable& table1) {
		// Initialize the nearest synonym to be the start of the path (synonym1)
		const std::string *nearestSynonym = &synonym1;
		const std::string *currentSynonym = nearestSynonym;
		const std::string *nextSynonym = &pathMap.at(*currentSynonym);
		while (*nextSynonym != synonym2) {
			// Traverse the path until we reach synonym2, checking if the nextSynonym is the 
			// new nearestSynonym.
			// It is the new nearestSynonym if it exists in table1!
			if (table1.doesHeaderExist(*nextSynonym)) {
				nearestSynonym = nextSynonym;
			}
			currentSynonym = nextSynonym;
			nextSynonym = &pathMap.at(*currentSynonym);
		}
		//cout << "findNearestSynonym(): nearest synonym for <" << synonym1 << "," << synonym2 << "> is " << *nearestSynonym << '\n';
		return *nearestSynonym;
}

int ResultGraphTable::getEstimatedNumberOfTuples(const std::string &synonym1, const std::string &synonym2, DesignEntityType synType1, DesignEntityType synType2, PKB *pkb) {
	// Algorithm:
	// If synonym1 == synonym2, just take the indexes of synonym1
	// Else If synonym1 and synonym2 are not related, just take the indexes of synonym1 * synonym2
	// Else If synonym1 and synonym2 are related,
	//	find the path from synonym1 to synonym2,
	//	and take the product of all the connecting edges between each pair of synonyms along the path.
	if (synonym1 == synonym2) {
		// just take the indexes of synonym1
		return getResultIndexesForSynonym(synonym1, synType1, pkb).size();

	} else if ( !isSynonymRelatedToSynonym(synonym1, synonym2)) {
		// just take the indexes of synonym1 * synonym2
		return (getResultIndexesForSynonym(synonym1, synType1, pkb).size() 
			* getResultIndexesForSynonym(synonym2, synType2, pkb).size());

	} else {
		// find the path from synonym1 to synonym2,
		// and take the product of all the connecting edges between each pair of synonyms along the path.
		const PathMap *pathMap = &findPathFromSynonymToSynonym(synonym1, synonym2);
		std::string currentSyn = synonym1;
		std::string nextSyn = pathMap->at(currentSyn);
		// Initialize the product
		int product = getCountOfAdjacentEdgesBetween(currentSyn, nextSyn);
		while (nextSyn != synonym2) {
			currentSyn = nextSyn;
			nextSyn = pathMap->at(currentSyn);
			product *= getCountOfAdjacentEdgesBetween(currentSyn, nextSyn);
		}
		return product;
	}
}

// Gets all the nodes that the specified node must use to check for bad edges
std::vector<const ResultGraphTableNode*> ResultGraphTable::getBadEdgeCheckingNodes(const ResultGraphTableNode& currentNode) {
	return std::vector<const ResultGraphTableNode*>(); // STUB TODO
}